# Combinatorics Example Problem

Ten weight lifters are competing in a team weightlifting contest. Of the lifters, 3 are from the United States, 4 are from Russia, 2 are from China, and 1 is from Canada.

Part 1
If the scoring takes account of the countries that the lifters represent, but not their individual identities, how many different outcomes are possible from the point of view of scores?

This part I understand: 10! / [ 3! 4! 2! ] = 12,600

Part 2 (don't understand this part)
How many different outcomes correspond to results in which the United States has 1 competitor in the top three and 2 in the bottom three?

This part I'm confused. Here you have 10 slots.
The first three slots must be of some order: US, US, or [Russia, China, Canada].
The last three slots must be of some order US, [Russia, China, Canada], [Russia, China, Canada].

I thought the answer would be this: $\binom{3}{2} \binom{1}{1} * \frac{7!}{4!\ 3!\ 2!}$

My reasoning: In the first 3 slots, you have to pick 2/3 US people. Then you only have one remaining. You have 7! ways to organize the rest but have to take out repeats so you divide by factorials of repeats which is 4,3, and 2. But my middle term is wrong....

My research shows me answers of 2 forms but I can't understand it:
Method 1: $\binom{3}{1} \binom{3}{2} * \frac{7!}{4!\ 3!\ 2!}$

This case, I don't understand why there's a 3 in the second binomial, $\binom{3}{2}$. We already selected ONE US person so shouldn't it be $\binom{2}{2}$?

Method 2: $\binom{7}{2} \binom{3}{1} \binom{5}{4} \binom{3}{2} \binom{1}{1}$ ?

Sorry for the long post. Thanks again.

-

Part 2 is solved in two stages (using Method 1):

Stage 1: Let U represent a slot holding a US competitor, and let _ represent a slot holding a non-US competitor. The first three slots must be one of the following:

U _ _

_ U _

_ _ U

This is where the $\binom{3}{1}$ comes from, since we are choosing one of three slots to be the U slot. The middle four slots have to be _ _ _ _. There is only one way to do this—we could write this as $\binom{4}{0}$ since we are choosing zero of the four slots to be U slots, or we could simply omit this factor. The last three slots must be one of the following:

U U _

U _ U

_ U U

This is where the $\binom{3}{2}$ comes from: we are choosing two of three slots to be U slots.

Stage 2: We now have a slot arrangement, of which _ U _ _ _ _ _ U U _ is an example. (There are a total of nine possibilities.) We now have to fill the blank slots with the three non-US nationalities. There are $\frac{7!}{4!\,2!\,1!}$ ways to do this.

Note: Since we only care about which nationality occupies which slot, and not which individual competitor, at no stage should we be selecting individual competitors from the set of competitors of a given nationality. I think this is where you went wrong. (You selected two particular US competitors from the set of three US competitors. There is no reason to do this.)

Alternative solution: I think Method 1 is a bit confusing because in Stage 1 we are choosing slots, whereas in Stage 2 we are permuting nationalities and dividing out repeats. A more uniform method would be to think of the entire process as one of choosing slots. If we take this point of view, there there are

• $\binom{3}{1}$ ways to choose one of the first three slots for the US.
• $\binom{3}{2}$ ways to choose two of the last three slots for the US.
• $\binom{7}{2}$ ways to choose two of the slots not yet assigned for China.
• $\binom{5}{4}$ ways to choose four of the slots not yet assigned for Russia.
• $\binom{1}{1}$ way to choose the remaining unassigned slot for Canada.

I believe this is what's going on in Method 2, although they wrote the factors in an unnatural order.

-
Thanks Will. I understand your stage 1 explanation--its fantastic. However, your Alternative Solution is not entirely clear to me. From your explanation, I now understand the terms $\binom{3}{1}$ and $\binom{3}{2}$. However, the rest of the terms are still not clear to me. For instance, why did choose to fill in the slots in the order that you did: China, Russia, and then Canada. What if someone wanted to fill in the slots in this order: Russia, China, and Canada. Then it would be $\binom{7}{4}\binom{5}{2}\binom{1}{1}$. Right? Then you wouldn't get the same answer. – user1527227 Apr 23 '13 at 18:19
Basically, why do you allow China to have 7 slots? Why not give the 7 to Russia first if someone wanted to fill in Russia? – user1527227 Apr 23 '13 at 18:45
It, in fact, does not matter in which order you place the nationalities, but if you do it in your order: Russia, China, Canada, then the expression would be $\binom{7}{4}\binom{3}{2}\binom{1}{1},$ which does equal $\binom{7}{2}\binom{5}{4}\binom{1}{1}$. This is because the products "telescope" so that there is systematic cancellation between the denominator and numerator of successive factors. So, for example, the expression $\binom{7}{2}\binom{5}{4}\binom{1}{1}$ can be written $\frac{7!}{2!\,5!}\frac{5!}{4!\,1!}\frac{1!}{1!\,0!}=\frac{7!}{2!\,4!\,1!}$ where we have cancelled factors$\ldots$ – Will Orrick Apr 23 '13 at 18:54
$\ldots$of $5!$ and $1!$, and dropped the factor of $0!$ in the denominator. The expression $\binom{7}{4}\binom{3}{2}\binom{1}{1}$ telescopes similarly: $\frac{7!}{4!\,3!}\frac{3!}{2!\,1!}\frac{1!}{1!\,0!}=\frac{7!}{4!\,2!\,1!}$. You always get $\frac{7!}{2!\,4!\,1}$ with the denominator factors permuted depending on which nationality gets placed first. So if we do Canada, China, Russia, we get $\binom{7}{1}\binom{6}{2}\binom{4}{4}=\frac{7!}{1!\,2!\,4!}$. – Will Orrick Apr 23 '13 at 18:54
@user1527227 : Basically the second denominator factor in each binomial coefficient cancels with the numerator of the next binomial coefficient, except for the last one, where this factor is always $0!$. Therefore you always get the same answer as you get by the divide-out-repeats method. Also, you aren't "allowing China to have 7 slots". What you're doing is giving 2 out of 7 slots to China. I also give 4 of those slots to Russia, but if since I do Russia second, I can't give them the 2 slots I already gave China. – Will Orrick Apr 23 '13 at 18:59

For the second, you pick the slots (not the people-we said all the people from one country were interchangeable) for the two US people in the bottom ${3 \choose 2}$ ways, but then have to pick which slot the US person in the top is in, which adds a factor ${3 \choose 1}$. Then of the seven left, you just have $\frac {7!}{4!2!}$ as there are no Americans among them. So Method 1 is off by the $3!$ in the denominator. I don't understand the terms in Method 2.

Added: One way to look at the first part, which I think is the way you did, is to say there are $10!$ orders of the people, but if the Americans are interchangeable you divide by $3!$, for the Russians you divide by $4!$ and for the Chinese you divide by $2!$. Another way would be to say we pick three slots for Americans in ${10 \choose 3}$ ways, then pick slots for the Russians in ${7 \choose 4}$ ways, then pick slots for the Chinese in ${3 \choose 2}$ ways, giving ${10 \choose 3}{7 \choose 4}{3 \choose 2}=120\cdot 35 \cdot 3=12600$. Of course the answer is the same, but the approach is better suited to the second part. Now if you think of choosing slots for nationalities you get what I did before.

-
I'm still lost... – user1527227 Apr 19 '13 at 23:27
Can anyone else explain the second part of the question? I still don't understand. Thanks. – user1527227 Apr 19 '13 at 23:59