How many ways are there to distribute n **different** toys among n **different** children so that each child gets at least one toy?

Question

The prompt:

How many ways are there to distribute n different toys among n different children so that each child gets at least one toy?

Is it appropriate to use bars and stars in this case?

Considering I use bars and stars, the n different toys will be the stars and n different children will be the bars.

After giving each of the n children 1 toys, we are left with 0 toys to distribute? This part confuses me.

Another approach I followed was choosing 1 child from the n children and giving him/her 1 toy from the n toys we have, gives us$${{n}\choose{1} }{{n}\choose{1}}$$ Is there only 1 way to give n different children n different toys so each gets 1 toy?

Answer 1

In this case the number of ways to distribute n different toys among n different children is simply n!

Indeed imagine to have the n toys in a row then you can distribute the n children in front of them in n! different ways.

Answer 2

The answer is $n!$ and the phrase "at least" is confusing I think.

If you consider the toys as a set $A$ and children as another set $B$ (since they are distinct, you can consider them as elements of sets), this distribution is number of bijections $A \to B$, which is $n!$ because for the first child, there is $n$ different options, for the second child, $n-1$, and so on. So in the end, we have $$n\cdot(n-1)\cdot(n-2)\cdot...2 \cdot 1 = n!$$ different distributions in total.

Note that stars and bars is used when you have for example indistinguishable toys and distinguishable children. We cannot use sets there because indistinguishable objects are the same and we cannot hold same objects in a set due to the definition of set.

Answer 3

The important part is that both children and toys are distinct.

Is there only 1 way to give n different children n different toys so each gets 1 toy?

That would be the answer if neither childen nor toys were distinct.

Now, let's start distributing toys to children. For the first child we can choose among n toys. For the second child we can choose among n-1 toys. If we continue like that, for the i-th child we have n-i+1 choices and for the n-th child we have only one toy left. In total we had $n(n-1)(n-2)\cdots 2\cdot 1= n!$ choices.

Another way to see it is by considering a function $f$ assigning toys to children. This would be a function $f: [n] \rightarrow [n]$, where $[n]=\{1,2,\ldots n\}$. Every toy can only be assigned to one child, so it makes sense to consider that function (it is well defined). We want every child to get a toy, thus the function must be onto (surjective). Since the cardinality of the domain and the image is equal (and finite) and the function is surjective, we have that $f$ is a bijection. In other words we are looking for all bijections from $[n]$ to itself. These functions are called permutations and it is well known that there are $n!$ of them.

A nice way to think of the different cases (distinct or not, surjective functions, etc) is the 12-fold way. See this and this. (note $S(n,n)=1$)

Answer 4

No, this is definitely not a case for stars and bars, for you use stars and bars when the objects are indistinguishable.