4
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Bram28
    Mar 21 '17 at 20:22
  • $\begingroup$ The answer: $n!$. $\endgroup$ Mar 21 '17 at 20:29
  • $\begingroup$ ohh am daamn sorry...yes I meant "distributing $n$ items to $r$ people". I changed the title. $\endgroup$
    – anir
    Mar 22 '17 at 4:29
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – anir
    Mar 26 '17 at 11:33

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.