Medium difficulty combinatorics problem with strange answer

Question

(Brazil National Olympiad)

Let $n$ be a positive integer. In how many ways can we distribute $n+1$ toys to $n$ kids, such that each kid gets at least one toy?

My approach:

For each child we can assign a number $k$ to it, representing the toy it will get. So we have ${n + 1} \choose {n}$ choices for chosing the toys, then $n!$ ways to choose the assignment. Since we have already chosen the leftover toy (by chosing the ones who were not left over), we now only have to choose from $n$ children who's getting it. So the final answer should be:

$(n+1)!n$

But the answer is: $\frac{(n+1)!n}{2}$

Can someone explain what was my mistake?

Answer 1

One may distribute toys in 3 steps:

1. [$n$ ways] Choose one kid of $n$;
2. [$\binom{n+1}{2}$ ways] Give him two of $n+1$ toys;
3. [$(n-1)!$ ways] Distribute remaining $n-1$ toys to $n-1$ kids (one toy to one kid). .

Multiplying counts of ways to perform each step we get $\frac{(n+1)!n}{2}$ ways at all, as needed.

Answer 2

A standard combinatorial way to think about it would be to recognize the role of the Stirling Numbers of the Second Kind. We proceed as follows:

(1) partition the set of $n+1$ toys into $n$ nonempty subsets. This is a Stirling number of the second kind ${n+1}\brace{n}$), which is here simply choosing two toys to group together (${{n+1}\brace{n}} = {{n+1}\choose{2}}$). Then

(2) Bijectively assign the $n$ children to the $n$ elements of the partition in $n!$ factorial ways.

Moreover, this generalizes immediately to the problem: How many ways are there to assign $m$ toys to $n$ children so that every child gets at least one toy? It's just ${{m}\brace{n}}n!$.