Distributing n different items to r different people with everyone getting at least one item

sorry cannot comment _ answer already here Distributing $n$ different things among $r$ persons

Sum of digits of permutations and combinations of a given set of digits

I was trying to come up with solution for this. First I tried to find number of ways in which $n$ distinct things can be distributed to $r$ different persons. This should be $r^n$. This can be explained as follows:

• First item can be assigned to any of the $r$ persons,
• Second item can be assigned to any of the $r$ persons and so on.

Thus we get, $\underbrace{r\times r \times ... \times r}_{\text{n times}}=r^n$

Then I thought of ways in which n distinct things can be distributed to r different persons so that every person gets at least one should be $r^n-({}^rP_1+{}^rP_2+...+{}^rP_{r-1})$, where ${}^rP_x$ is the number of ways $x$ persons does not get any item. However, later I felt that I am not correct with "${}^rP_x$ is the number of ways $x$ persons does not get any item". It should be ${}^rP_x\times (r-x)^n$ as there are ${}^rP_x$ ways to choose persons who don't get any item and we can distribute the $n$ items to the remaining persons in $(r-x)^n$ ways. So the final solution can be:

$r^n-({}^nP_1 \times (r-1)^n +{}^nP_2 \times (r-2)^n+...+{}^nP_{n-1}\times (r-(r-1))^1)$

This looks very bad to me. Am I correct with this? Is there any better solution?

• Your title says to distribute n items to n people ... which would be just $n!$ But your text suggests you want to distribute n items to r people? Is your title wrong? Mar 21 '17 at 20:22
• The answer: $n!$. Mar 21 '17 at 20:29
• ohh am daamn sorry...yes I meant "distributing $n$ items to $r$ people". I changed the title.
– anir
Mar 22 '17 at 4:29

Answer is $S(n,r) \times r!$ where $S(n,r)$ is Stirling number of the second kind, which is the number of ways to partition a set of $n$ objects into $r$ non-empty subsets. You can read more about it here
i don't think there is no easy way around. But, depending in the values of $n$ and $k$, certain values for $S(n,r)$ are easy to find.
• Want to what count will be if I replace "at least one" with "zero or more". One of my textbook says its $\Sigma_{k=1}^rk!S(n,k)$ where number of non empty groups are $1,2,...,r$, while other source says its $r^n$ (since each of $n$ items can be given to one of $r$ people which may lead to some person getting zero item). While looking at their respective reasoning I feel both are correct. But then which one is wrong?