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.

In a soccer tournament of 15 teams, the top three teams are awarded gold, silver, and bronze cups, and the last three teams are dropped to a lower league. We regard two outcomes of the tournament as the same if the teams that receive the gold, silver, and bronze cups, respectively, are identical and the teams which drop to a lower league are also identical. How many different possible outcomes are there for the tournament?

I have no idea, is this a question permutations and combinations? As in how can I order (permute) the 6 teams in between the first and last 3? Which I would think would be P(6,6) = 6!

I'm not sure how to order the first and last 3, is it just 6 choose 3 for the first 3, and then 3 choose 3 for the last 3? By multiplication principle: (6 choose 3)*6!

share|improve this question

2 Answers 2

up vote 1 down vote accepted

You are dividing 15 teams into 5 classes:

  1. Gold (1 team)
  2. Silver (1 team)
  3. Bronze (1 team)
  4. Bottom three (3 teams)
  5. All the rest (9 teams)

This is similar to putting $15$ balls into $5$ bins, with three bins of size $1$, one bin of size $3$ and one bin of size $9$. For this you need the multinomial coefficient. In particular, the interpretation of these coefficients is:

The multinomial coefficients have a direct combinatorial interpretation, as the number of ways of depositing $n$ distinct objects into $m$ distinct bins, with $k_1$ objects in the first bin, $k_2$ objects in the second bin, and so on.

Taking $n = 15$ teams, $m = 5$ classes and $k_1 = k_2 = k_3 = 1$, $k_4 = 3$ and $k_5 = 9$ we thus get the number we need. This is

$$\binom{15}{1,1,1,3,9} = \frac{15!}{1!\cdot 1!\cdot 1!\cdot 3!\cdot 9!} = 600600$$


Edit: If you interpret the question as counting medalists as a single class, you instead get three classes:

  1. Medal (3 teams)
  2. Bottom three (3 teams)
  3. All the rest (9 teams)

In that case you get $n = 15$, $m = 3$ and $k_1 = k_2 = 3$, $k_3 = 9$. So then the answer is:

$$\binom{15}{3,3,9} = \frac{15!}{3!\cdot 3!\cdot 9!} = 100100 = \frac{1}{3!} \binom{15}{1,1,1,3,9}$$

This is also what we expect: Every solution from the second interpretation is counted $3! = 6$ times in the first interpretation, so we get $6$ times less combinations.

share|improve this answer
    
So multinomial coefficients are the same as calculating the r-permutations of a multiset S with objects of k different types with finite repetition numbers n1, n2,...,nk and |S| = n1 + n2 +... + nk? –  Gbean Sep 20 '11 at 0:55

Imagine all the team captains are standing in front of you. There are fifteen teams to which you can give the gold cup. After that, there are fourteen teams remaining that can receive the silver cup. Finally, there are thirteen teams remaining that can receive the bronze cup.

Now, we have twelve teams remaining and must choose three of them to drop. Since the order of our choice does not matter here, there are $\binom{12}{3}$ ways to drop the teams.

Multiplying everything together, there are $15 \cdot 14 \cdot 13 \cdot \binom{12}{3}$ possible outcomes.

share|improve this answer

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.