Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

These are two problems from my combinatorics assignment that I'm not quite confident in my answer. Am I thinking of these the right way?


Problem 1: On rolling 16 dice. How many of the $6^{16}$ possible (ordered) outcomes would contain exactly three quadruplets? (the same number appearing four times.)

Answer: There are $ \binom{16}{4, 4, 4, 1, 1, 1, 1} $ ways to choose the dice (four quadruplets and four singlets).

There are $\binom{6}{3}$ possible values the quadruplets can have.$^1$

The possible values of the singlets can repeat, yielding $3^4$ in total. But three of those combinations would be such that they all have the same value; and we can't have another quadruplet. So the number of possible values for the singlets must be $3^4 - 3$.

Thus, the total number of possible values is

\begin{equation*} \binom{16}{4,4,4,1,1,1,1} \binom{6}{3} (3^4 - 3) = 2 \, 361 \, 078 \, 720 \, 000 \end{equation*}


  1. I think this should be changed to $\frac{6!}{3!}$ instead of $\binom{6}{3}$?

problem: Four friends and 21 boys are to be randomly divided into five teams of 5 players. How many of the $\binom{25}{5,5,5,5,5} \frac{1}{5!}$ possible ways of creating five teams will have each of the four friends play for a different team?

Answer: There are $\frac{4!}{4!}$ ways to distribute the four friends into four teams. There are $\binom{21}{1}$ ways to choose a leader for the fifth team from the remaining $21$ kids.

There are $\binom{20}{4,4,4,4,4} \frac{1}{5!}$ ways to distribute the remaining $20$ kids among the five teams.

This yields a total number of possible teams:

\begin{equation*} \frac{4!}{4!} \binom{21}{1} \binom{20}{4,4,4,4,4} \frac{1}{5!} = 3 \, 547 \, 982 \, 095 \, 257 \, 600 \end{equation*}


share|improve this question
    
I wrote out an analysis of the first problem. The answer is again different. –  André Nicolas Sep 22 '11 at 1:31
add comment

2 Answers

up vote 3 down vote accepted

The following is an analysis of the second problem. It yields a somewhat different answer. Added: It is followed by an analysis of the first problem, again yielding a somewhat different answer.

Let the four friends be called A, B, C, and D. Of these four, A is the leader, her friends always let her go first. And B is second in status. Then comes C, with poor D always last. Sad, you may think, but irrelevant. However, it will turn out that the pecking order of the four friends is useful for correct counting. (The character analysis is borrowed from Stephen Leacock's essay "A, B, and C.")

First the coach chooses the $5$ people who will not have one of the friends on their team. This can be done in $\binom{21}{5}$ ways.

Now A picks from the remaining $16$ people the $4$ people who will be on her team. This can be done in $\binom{16}{4}$ ways. Once A is through choosing, it is B's turn to choose. For each choice that A made, B has $\binom{12}{4}$ choices. Continue. We get that the number of choices is $$\binom{21}{5}\binom{16}{4}\binom{12}{4}\binom{8}{4}\binom{4}{4}.$$ This can be simplified to $$\frac{21!}{5!4!4!4!4!},$$ and then we could compute.

Added: I had not looked at the first problem, since there seemed to be agreement about the answer. But here is an analysis. I take it that $3$ quadruples means that there are $3$ numbers that occur exactly $4$ times each (but not necessarily in a row), and no other number occurs $4$ times. (The other two analyses also make this assumption.)

The $3$ numbers that will appear $4$ times can be chosen in $\binom{6}{3}$ ways. Now suppose we have done the choosing, and that the chosen numbers, listed in increasing order, are $p$, $q$, and $r$. Choose the places that the $p$'s will go. This can be done in $\binom{16}{4}$ ways. For each such choice, there are $\binom{12}{4}$ ways to choose where the $q$'s will go, and for each such choice there are $\binom{8}{4}$ ways to choose where the $r$'s will go. Once we have done that, there are, as in the OP's analysis, $3^4-3$ ways to fill in the remaining open slots. We get therefore a total of $$\binom{6}{3}\binom{16}{4}\binom{12}{4}\binom{8}{4}(3^4-3).$$ To compare with the other answers, we simplify a little, to $$\binom{6}{3}\frac{16!}{4!4!4!4!}(3^4-3).$$

Comment: Maybe multinomial coefficients are slightly more tricky to work with than combinations of binomial coefficients. In the first problem, once the locations of the $3$ quadruples have been determined, all that remains is to fill in the remaining $4$ spots: no choosing of $1$ spot then $1$ spot then $1$ spot then $1$ spot is involved.

share|improve this answer
    
So this would be equivalent to dividing my result by $4!$ and $3!$. I'm trying to see what that would mean so I know where I went wrong, but I can't picture it. — It makes sense the way you arrive at it though. –  iDontKnowBetter Sep 22 '11 at 3:04
    
In the first problem, the difference is clear. After choosing the positions of the three groups of $4$, you picked $1$ more point, then another, and so on. That's where the multinomial $\binom{16}{4,4,4,1,1,1,1}$ comes from, and where the error is, the source of the extra extra $(4)(3)(2)(1)$. Apart from the multinomial issue, your analysis was clear and good. The team stuff is subtler. If we want to divide $10$ people into $2$ basketball teams, one to wear blue and the other red, we get one answer. If you just want to divide them into $2$ teams, the answer is different. –  André Nicolas Sep 22 '11 at 4:11
add comment

Your first answer is right after you make the correction in the footnote: the order of the quadruples does matter.

In the second problem you can’t simply pick a team leader for the fifth team: that counts that team five times, since any member of it could be the leader. I’d analyze it as follows. There are $\binom{21}{5,4,4,4,4}$ ways to split the $21$ boys into a team of $5$ and four teams of $4$, and there are $4!$ ways to assign the friends to the teams of $4$, for a total of $$\binom{21}{5,4,4,4,4} 4! = \frac{21!4!}{5!4!4!4!4!} = \frac{21!}{5!4!4!4!} = 30,798,455,688,000$$ ways of creating the five teams.

Added: I slipped up here. $\binom{21}{5,4,4,4,4}$ actually counts the number of ways to pick the team of $5$ and then to pick the other four teams in a particular order, so we have to divide by $4!$ to get the number of ways to split the $21$ boys into a team of $5$ and four (unordered) teams of $4$ each. Then there are $4!$ ways to pair the friends with the short-handed teams, so the final result should be simply $$\frac{\binom{21}{5,4,4,4,4}}{4!} \cdot 4! = \binom{21}{5,4,4,4,4} = 1,283,268,987,000.$$

Of course as André points out in his solution, we might as well have picked the teams in a particular order to begin with $-$ perhaps in alphabetical order of the friends’ names.

share|improve this answer
    
Oh, I see. Something didn't seem right with my solution. Thanks. –  iDontKnowBetter Sep 22 '11 at 0:45
    
Question: don't I have to divide your result by $5!$? Since they are not being assigned to specific teams and order doesn't matter. –  iDontKnowBetter Sep 22 '11 at 0:54
    
@fakaff: I haven’t counted different orders of the $5$ teams separately. I do have to divide by $4!$, because I inadvertently did count different orders of the $4$ teams with the friends, but I’ve fixed that in the revision. –  Brian M. Scott Sep 22 '11 at 1:00
    
Oh, of course :) thanks again. –  iDontKnowBetter Sep 22 '11 at 1:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.