# Choosing 5 elements from a set of 13

We have 13 toys and we want to give them to 5 children.

a) In how many ways if every toy is different and every child gets exactly one?

b) In how many ways if every toy is the same and every child gets at least one?

My try:

a) The way I see it it is:

$$13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 = 154440$$

b)$$\binom{13}{5} + \binom{13}{4} + \binom{13}{3} + \binom{13}{2} + \binom{13}{1}$$

However I do not know if it is correct.

From the context I do not exactly know when the order matters. I suppose that if the toys are different, that it matters, but on the other hand every child is different too.

What is the correct thinking approach ?

• Your answer to the first question is correct. In the second question, must all the toys be distributed? Commented Nov 23, 2021 at 22:02
• @N.F.Taussig Yes all toys must be distributed. I see that my second answer is wrong. What would be the correct approach?
– VLC
Commented Nov 23, 2021 at 22:04

In how many ways can $$13$$ identical toys be distributed to five children if each child receives at least one toy?

Let $$x_i$$, $$1 \leq i \leq 5$$, be the number of toys the $$i$$th child receives. Then $$x_1 + x_2 + x_3 + x_4 + x_5 = 13 \tag{1}$$ is an equation in the positive integers. A particular solution of equation 1 corresponds to the placement of $$5 - 1 = 4$$ addition signs in the $$13 - 1 = 12$$ spaces between successive ones in a row of $$13$$ ones.
$$1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1$$ For instance, if we place addition signs in the first, third, sixth, and tenth positions, then we obtain $$1 + 1 1 + 1 1 1 + 1 1 1 1 + 1 1 1$$ which corresponds to the solution $$x_1 = 1, x_2 = 2, x_3 = 3, x_4 = 4, x_5 = 3$$. The number of such solutions is the number of ways we can place four addition signs in the twelve spaces between successive ones in a row of thirteen ones, which is $$\binom{13 - 1}{5 - 1} = \binom{12}{4}$$

The alternative Stars and Bars approach, which is also discussed here is:

The desired computation is the number of solutions to

• $$x_1 + x_2 + x_3 + x_4 + x_5 = 13$$

• $$x_1, x_2, \cdots, x_5 \in \Bbb{Z_{\geq 1}}.$$

In general, if the 2nd constraint above is changed to $$x_1, x_2, \cdots, x_5 \in \Bbb{Z_{\geq 0}}$$, and the $$(13)$$ is changed to $$(n)$$, then the number of solutions is $$\displaystyle \binom{n + [5-1]}{5-1} = \binom{n + 4}{4}.$$

For $$i \in \{1,2,\cdots,5\}$$, let $$y_i = (x_i) - 1.$$

Then, the problem bijects (i.e. the number of solutions remains the same) to

• $$y_1 + y_2 + y_3 + y_4 + y_5 = (13 - 5) = 8.$$

• $$y_1, y_2, \cdots, y_5 \in \Bbb{Z_{\geq 0}}.$$

So, the number of solutions to the original problem is

$$\displaystyle \binom{8 + 4}{4} = \binom{12}{4}.$$