# How to distribute $k$ prizes in $p$ student with each student would receive $(k-1)$ prizes at most?

A teacher decided to encourage the kids by distributing prizes to them. Each of the prizes was different from the other. The total number of prize was $k$, and total number of kids was $p$. To encourage the kids, the number of prizes was more than the number of kids. But, the teacher imposed a restriction on herself that each kid would receive $(k – 1)$ prizes at the most. How many ways she could distribute the prizes?

Answer is $p^k-p$

If I understood the problem correctly, it is no-where stated that a student can get no prize at all, and the answer seems to be using this assumption,however I am a bit confused why the answer is not $p^{k-1}$?

If the restriction is that no student can get more than $(k-1)$ prizes then what is wrong with starting with $(k-1)$ distinct prizes and distributing those into $p$ distinct groups (students)?

-
Then what happens with the last prize? That one needs to be distributed too, right? But then it makes a difference if the first k-1 prizes went to a single student or more students... – N. S. Nov 6 '11 at 23:34

Suppose there were no restrictions whatsoever and the problem simply said "How can you distribute $k$ prizes among $p$ students?".

For each prize, there are $p$ possibilities for the recipient of that prize. In total, that means there are $p \cdot p \cdot \dots \cdot p$ (with $k$ copies of $p$ in the product) possible ways to assign the prizes. This is the $p^k$ part.

Now let's impose the restriction that no student receives all the prizes (this is the same as saying no student receives more than $k-1$ prizes). Of the $p^k$ configurations we just enumerated, which ones are illegal under this new restriction? Exactly $p$ of them, since there is one illegal configuration for each student (namely, giving that student all the prizes).

Subtracting the illegal configurations from our previous enumeration, we get $p^k - p$ legal configurations.

-
But what I wanted to know is what is wrong with $p^{k-1}$? – Quixotic Nov 6 '11 at 23:31
If you simply distribute $k-1$ prizes into the $p$ students, you still have a prize remaining to give out. When you try to give that last prize, you'll have to worry about the case that you are giving it to a student who already has $k-1$ prizes. – Austin Mohr Nov 6 '11 at 23:34
Thanks that rests my doubts :) – Quixotic Nov 6 '11 at 23:37
Just trying to vary the parameters ..in general if we have to distribute k (distict) prizes into p (distinct) students so that no student can get more than (k-n) prizes is $p^k-n \times p$, isn't?! – Quixotic Nov 7 '11 at 0:22
@MaX It is not quite so simple, and to elaborate would be a whole answer unto itself. In your original problem, there was only one way a student could get too many prizes (namely, he received all the prizes). In your new version, there are many ways a student can receive too many gifts and also many students can simultaneously receive too many gifts. If you are interested, you might post your new version as it's own question. – Austin Mohr Nov 7 '11 at 0:43

The answer can easily be seen with this reasoning: there are p students and k prizes, so the total number of ways the prizes can be distributed is $p^k$ (for each of $k$ prizes, there are $p$ different students to whom it can be given). However, with the added constraint that no student can receive every prize, we must eliminate $p$ of those possibilities (one for when each student receives all of the prizes). Therefore the total number of ways is $p^k - p$.

We can't simply start with $k - 1$ prizes and distribute them to $p$ students because we would be missing the different cases that come from which student gets the last ($k^{th}$) prize.

-