1
$\begingroup$

The correct answer for this question is $m^n-m$ and it is found out by subtracting the number of ways in which one person receives all the prizes from the total number of ways of distributing the prizes.

However, when I was attempting the question, I thought, that since we’re distributing the prizes each person should get at least one prize and at most $n-1$ prizes hence there are $n-1$ ways of giving prizes to one person. However since there are $m$ persons, we can hence distribute the prizes in $(n-1)^m$ ways. However, this method is wrong. Just wanted to clarify, is this method wrong because it is not possible for each person to receive $n-1$ prizes? If one person gets $n-1$ prizes then there will be only $1$ prize remaining for the rest hence it wouldn’t be called distribution. However, this method could work if we have $2$ people and $2$ prizes right?

$\endgroup$
2
$\begingroup$

We are choosing recipients for the prizes. For each of the $n$ prizes, there are $m$ possible recipients. Hence, if there were no restrictions, there would be $m^n$ ways to distribute the prizes. The restriction that no person receives all the prizes means we have to eliminate those $m$ cases, yielding $m^n - m$ permissible distributions of prizes.

I thought that since we're distributing the prizes each person should get at least one prize ...

We cannot assume that each person receives a prize. If we did make that assumption, we would have to use the Inclusion-Exclusion Principle to exclude those cases in which at least one person does not receive a prize. There are $\binom{m}{k}$ ways to exclude $k$ of the $m$ possible recipients and $(m - k)^n$ ways to distribute the prizes to the remaining $m - k$ people. Thus, there are $$\sum_{k = 0}^{m} (-1)^k\binom{m}{k}(m - k)^n$$ ways to distribute the prizes if each person receives at least one prize.

... each person receives at most $n - 1$ prizes, hence, there are $n - 1$ ways of giving prizes to one person

There are $n$ ways of giving $n$ prizes to one person, once for each of the $n$ ways we could exclude one of the prizes.

... there are $m$ prizes, so we can distribute the prizes in $(n - 1)^m$ ways.

We are choosing recipients for the prizes, so we have $m$ choices for each prize. Also, each prize can be distributed only once.

Is this method wrong since it is not possible for each person to receive $n - 1$ prizes?

That is one reason it is wrong.

However, this method could work if we have $2$ people and $2$ prizes right?

If we have two people and no person receives both prizes, each person receives one prize, so there are $2!$ ways to distribute the prizes. Notice that $2^2 - 2 = 2!$.

Your method gives $(2 - 1)^2 = 1^2 = 1$ way to distribute the prizes, which would make sense if the prizes were identical. However, they are not.

$\endgroup$
  • $\begingroup$ Thank you , but doesn’t distribution mean that each person should receive atleast one ? Or is it not necessary at all ? $\endgroup$ – Aditi Oct 22 '17 at 16:13
  • $\begingroup$ It is not necessary that each person receive at least one. Making that assumption makes the problem much harder. $\endgroup$ – N. F. Taussig Oct 22 '17 at 16:21
  • $\begingroup$ Okay thanks for the clarification! $\endgroup$ – Aditi Oct 22 '17 at 16:25
1
$\begingroup$

The number of ways to distribute $n$ prizes to the $m$ people without restriction is $m^n$ (since each prize can go to $m$ people). The number of ways to distribute the prizes so that some person gets all $n$ prizes is $m$ (as there are $m$ people). Hence the number of ways to distribute the $n$ prizes to the $m$ people so that every person gets less than $n$ prizes is $$ m^n-m. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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