1
$\begingroup$

In how many ways can you distribute $n$ different things to $r$ different persons each getting at least one??

I approached the problem like this:

Let's first give $1$ thing to each of the $r$ different persons,so that we don't have to bother about anybody getting none. Then we can distribute the remaining $n- r$ items in $r^{n-r}$ ways.

But this does not give the correct answer. What is wrong? What should I do?

$\endgroup$
  • $\begingroup$ I think your problem is that you have not dealt with the fact that the things are different. So it matters how you distribute those first things one to each person. If you edit the question to show more of your work we can tell whether that's where you went wrong. $\endgroup$ – Ethan Bolker Sep 27 at 13:40
  • $\begingroup$ Oh! I see. But how can I can into account the ways of distributing those first things? $\endgroup$ – Rinkiny Sep 27 at 13:42
  • $\begingroup$ I didn't quite see your mistake. @JMoravitz got it right in his answer. $\endgroup$ – Ethan Bolker Sep 27 at 13:52
2
$\begingroup$

You made a mistake in applying the rule of product and overcounting certain scenarios.

The answer your logic leads you to gives an answer of $n\frac{r}{~}\cdot r^{n-r}$ is the answer to the question of "How many ways can you distribute $r$ different items to $n$ different people so that each person gets exactly one item that they put in their pocket and might get additional items which they put on the floor in front of them."

The point here is that an outcome where Mr. A gets items #1 and #2 but item #1 is in his pocket while #2 is on the floor is different than an outcome where Mr. A gets items #1 and #2 but has #2 in his pocket instead while #1 is the item on the ground when we really in our original problem want to consider these as the same outcome.

If you remain unconvinced of this, then see what happens if we set $r$ equal to $1$ and we have $n$ items but only one person. Clearly there should be only one possible outcome, but your logic would have you believe there are $n$ possible outcomes.


A correct approach: use Inclusion-Exclusion based on the sets where a person doesn't get any items.


There is a shorthand for the final result by using Stirling Numbers of the Second Kind.

There will be $\left\{\begin{matrix}n\\r\end{matrix}\right\}\cdot r!$ possible ways to partition $n$ distinct items into $r$ distinct labeled subsets.

$\endgroup$
  • $\begingroup$ Thanks for explaining. But can you please tell what Stirling numbers are? $\endgroup$ – Rinkiny Sep 27 at 17:28
  • $\begingroup$ @Rinkiny There is a link included above. Stirling numbers of the second kind (not to be confused with stirling numbers of the first kind) count the number of ways to partition a set of $n$ elements into $k$ nonempty unlabeled subsets. $\endgroup$ – JMoravitz Sep 27 at 17:30
  • $\begingroup$ Thanks. But how to solve this problem? $\endgroup$ – Rinkiny Sep 27 at 17:38
  • $\begingroup$ @Rinkiny there is a link included above... The solution is $\left\{\begin{smallmatrix} n\\r\end{smallmatrix}\right\} r!$. The link to the page about the stirling numbers of the second kind show a formula and give a proof for a formula involving a summation of terms of the form $(-1)^i\binom{k}{i}(k-i)^n$. To understand what and why that formula is what it is, refer to the first link provided on inclusion-exclusion. $\endgroup$ – JMoravitz Sep 27 at 17:42

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.