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?
Best Answer
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.