# How i can solve the combinatorial problem, using only the multiplicative and additive principle?

I have a statement:

In a class of 10 students, $3$ prizes will be awarded.

What is the total combination of awards, if:

$i)$ Each player receives a SINGLE prize and the prizes are different.

$ii)$ Each player receives a SINGLE prize and the prizes are the same.

$iii)$ A player can repeat all the prizes, and the prizes are the same.

Well, my development was:

Let the prizes, be called $A, B, C$

$i)$ The price $A$ have 10 players to be distributed, $B$ have 9 players, $C$ have 8 players, so the total cases are: $10*9*8 = 720$

$ii)$ The same argument for $i)$, but now the order doesn't matter, so I can assume that: $ABC = BCA = CBA$, because $A = B = C$....

Therefore, to undo the repeated combinations i need the permutation of $3$, so the total combinations will be: $\frac{10*9*8}{3!} = 120$

$iii)$ Well, with the formula of $C_{repetition}(n, r) = \frac{(n+r-1)!}{(n-1)!r!}$

The result will be: $C_{rep}(10, 3) = \frac{12!}{9!3!} = 220$

The three results are good, but with the exercise $iii)$ i have some problems of understanding.

$A)$ ¿How i can get the correct result of the third exercise, using only the multiplicative and additive principle, in a intuitive way?

$B)$ ¿What is the intuitive and the formal proof of the formula: $\frac{(n+r-1)!}{(n-1)!r!}$ ?

• There is something I don't get for ii)... if a student only receives 1 prize and the prizes are the same, each student will receive one prize and there is only one way to do it... – RGS Jul 31 '18 at 17:12
• Do we have $3$ or $10$ prizes? According to your calculations the number of prizes is $3$ – Vasya Jul 31 '18 at 17:16
• Yes $3$ prizes and $10$ students – Eduardo S. Jul 31 '18 at 17:17
• Sorry, question edited. – Eduardo S. Jul 31 '18 at 17:17
• look up "stars and bars" method for #3: en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) . You need to distribute 3 stars between 10 bins (9 bars). – Vasya Jul 31 '18 at 17:21

This is a tricky question to answer in general. Consider the following related problem:

There are $n$ distinct people and $r$ distinct hats. Each hat must be placed on a person. It is allowed to stack multiple hats on a single person; in the case, the order of the stack matters.

How many ways are there to place all the hats?

We can solve this using the multiplication principle. Place the hats one at a time, in the order hat 1, hat 2, ... , hat $r$.

1. Hat $1$ can be placed in $n$ ways, on any of the $n$ people.
2. Hat $2$ can either be placed directly on top of any of the $n$ heads, or on top of hat $1$. This is $n+1$ choices.
3. Hat $3$ can be placed on any of of the $n$ heads, or on hat $1$, or on top of hat $2$. This is $n+2$ choices.

You see the pattern. The $i^\text{th}$ hat has $n+i-1$ choices, so the number of ways is $$n(n+1)(n+2)\cdots (n+r-1)$$

Now, back to the problem of giving $r$ identical prizes to $n$ distinct people. This is just like the previous problem, but the $r$ items begin given out are no longer distinct. Therefore, we must divide by $r!$ in order to get rid of this over counting, resulting in $$\frac{n(n+1)(n+2)\cdots (n+r-1)}{r!}=\binom{n+r-1}{r}$$

Note the analogy between cases (i) and (ii); the result for (ii) was obtained by taking the result for (i) and dividing by $3!$ to account for the fact that we do no care about order.

• Thank you. I understand why you divide between $r!$ And the problem of hats, since you have 10 heads, and every time you put a hat on some head, it's like increasing 1 head. But, in my particular problem I see it different, like: The first prize can be divided between 10, the second 10 and the third 10 people. I mean, 10 ^ 3 and I would have to divide by the permutations. – Eduardo S. Jul 31 '18 at 20:53
• @Mattiu You are noticing the thing that makes this problem confusing. Unfortunately, the number of ways to give out identical prizes cannot be computed as the number of ways to give out distinct prizes divided by $r!$. The problem is that symmetry is broken when two prizes are given to the same person; if there are $n$ prizes, say, then there are $n!$ ways to give everyone a prize, but only one way to give all the prizes to a particular person. That is why you need to introduce the order of the hats; this fixes the symmetry, allowing you to divide by $r!$. – Mike Earnest Jul 31 '18 at 21:01
• @Mattiu Note that $n^r$ is in general not divisible by $r!$, for example $10^3/3!$ is not an integer. – Mike Earnest Aug 1 '18 at 16:27
• Thank you. Two things, could you solve the exercise according to your logic, for me to be able to understand it more? And secondly, where I find a demonstration of $n ^ r$ is not generally divisible by $r!$ (It looks interesting) – Eduardo S. Aug 1 '18 at 23:30
• (1) I challenge you to think through my answer, and apply it to the case n = 10, r = 3 on your own. (2) The whole demonstration is the single counterexample n = 10, r = 3. I don't think there is any deeper explanation. – Mike Earnest Aug 1 '18 at 23:56

One way is to break the $iii)$ into three scenarios: 1) Three players get a prize. 2) Two players get a prize (one gets two). 3) One player gets three prizes. Case one is the same as $ii)$. Case two is $10*9$. Case three is simply $10$.

• Why the $ii)$ case is $10 * 9$ ? I think that should be $(10 * 9)/3$, because $AAB = BAA = ABA$ – Eduardo S. Jul 31 '18 at 19:59
• @Mattiu There are ten ways to select the player who receives two prizes. For each such choice, there are nine ways to select which one of the other players receives one prize. – N. F. Taussig Jul 31 '18 at 20:22
• @N.F.Taussig: Exactly what I was typing. This is similar to distribute two distinct objects between $10$ people where one person can get one object at most – Vasya Jul 31 '18 at 20:25
• Yes, I understand. But how do you know if you're counting repeated elements or not? Per example, how you know if you're counting combinations like: $BAA - AAB - ABA$ that are the same combination. – Eduardo S. Jul 31 '18 at 20:36
• @Mattiu: yes, similarly $BBA=BAB=ABB$ so you only have two choices: $A$ gets $2$ prizes and $B$ gets $1$ or vice versa which is $2 \cdot 1$. – Vasya Jul 31 '18 at 20:51