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?
Best Answer
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.
To understand the values, you can refer the series A008277 in the OEIS.