Initially, it seems that the concepts of "permutations of sets with indistinguishable objects" and "distributing objects into boxes" aren't similar at all. However, due to the metaphysical funkiness of discrete mathematics, we'll see that the formulas for each of these cases are identical!! In this part of the tutorial, we'll work out an example of each type to derive the formulas and then try to figure out why they're exactly the same.
To pose a riddle, how many different strings can be made from the word 'connundrum'? Permutations will still be used to solve this question. However, there are some letters we don't want to count more than once. For example, the letter n is used three times but we can't tell the difference between each one. As far as we're concerned, the first n, the second n, and the third n all look like "n" when the order of the letters is changed. The first step in solving a problem like this is to identify all the unique items there are. For 'connundrum', thare are a total of - (1)
**c** - (1)
**o** - (3)
**n** - (2)
**u** - (1)
**d** - (1)
**r** - (1)
**m**
Additionally, let's remove all the letters from 'connundrum,' so that there are only the empty spot where the letters can go: _ _ _ _ _ _ _ _ _ _
Now, let's place the letters back in the empty slots. First, there's one 'c' which can be put in any of ten spots. Next, the 'o' can be placed among the remaining nine locations. Here is gets interesting: we have 3 'n's which can be put into any of the eight open blanks. Additionally, the 2 'u's can be placed in any of the 5 remaining, open slots. The problem is finished in the same manner. The expression described above can be written as follows:
A similar type of problem occurs when we want to determine how many ways we can put distinguishable objects into distinguishable boxes. This simply means that we can tell the difference between each item that we have and it matters where each item goes. For example, pretend you're playing 5-card stud poker with three of your friends. Aces are high, stakes are low, the pretzel bowl is empty, and you're waiting for your buddy to finish shuffling the deck. As he starts to deal, you wonder how many different ways there are to deal the hands. That is,
Initially there are 52 total cards, and 5 of those will be dealt to the first player. Thus, there are C(52, 5) possibilites for the first person. Next, player two will be dealt 5 cards from a total of 47. The number of possibilites for that individual event is C(47, 5). Similarly, there are C(42, 5) possibilities for the third person, and C(37, 5) for the fourth player. Therefore, the total number of possibilities is
(In the poker game, it is important to note that there are actually five boxes - the four players' hands and the deck. So, the first four boxes - the players' hands - each have 5 items; the fifth box - the deck - has 32 items.) Conclusion
As you can see, these two types of problems are very similar and their formulas are identical. This is possible once you think of the cards as indistinguishable objects, and the boxes are indistinguishable types. Once we do this, we can apply the conditions of the first example to our card problem.
$\begingroup$
The answer is $\frac{52!}{(5!\times 5!\times 5!\times 5!\times 32!)} = 1.4782628e+24$ This reminds me of that if I have to select 7 objects from 3 types with infinite supply: oo|oo|ooo I know that it's no necessary to use the bar in this question because each person has the same numbers of the cards, but I still want to try to add 4 bars. That is: 5 cards for person1 | 5 cards for person2 | 5 cards for person3 | 5 cards for person4 | undealt cars so the equation is: $\frac{56!}{(5!\times 5!\times 5!\times 5!\times 32!\times 4!)}=5.4295116e+29$ What's wrong with my idea? $\endgroup$ 3 |