Five different games are to be distributed among $4$ children randomly. The probability that each child get at least one game is?

Question

Here's a question :- Five different games are to be distributed among 4 children randomly. The probability that each child get at least one game is?

To find the answer, we will have to find the sample space. Here it is easy to find the sample space using PnC, since each game has an equal chance of being chosen, the sample space becomes $4^5$. My doubt is why can't we use multinomial theorem for this:- Let the first child get $x_1$ books, second one get $x_2$ and so on. So, we may say :-

$$x_1 + x_2 + x_3 + x_4 = 5$$

So, the number of non-negative integral solutions for this equation is:-

$$\binom{5 + 4 -1}{4 - 1}$$

This method gives the wrong answer. Where am I going wrong ?

Answer 1

As @drhab pointed out in a now deleted comment, the formula $$\binom{k + n - 1}{n - 1}$$ is used when distributing $k$ indistinguishable objects to $n$ distinct boxes. However, the objects in this problem are distinct.

Also, the outcomes to the equation $x_1 + x_2 + x_3 + x_4 = 5$ are not equally likely to occur. There are $\binom{5}{2}3! = 60$ ways to distribute the games to the four children so that the youngest child receives two games, while each of the other children each receive one. On the other hand, there is only one way to distribute all five games to the eldest child.

Since you mentioned, the multinomial theorem, notice that we could express the number of ways of distributing two games to the youngest child and one games each to each of the other children using the multinomial coefficient $$\binom{5}{2, 1, 1, 1} = \frac{5!}{2!1!1!1!}$$ and the number of ways of distributing all five games to the oldest child as $$\binom{5}{0, 0, 0, 5} = \frac{5!}{0!0!0!5!}$$

As you observed, there are four choices for each of the five games, so there are $4^5$ elements in our sample space.

For the favorable cases, observe that one child must receive two games, while each of the others receives one. To finish the problem, choose which of the four children receives two games, choose which two of the five games that child receives, and distribute one game each to each of the remaining three children.

This can be done in $$\binom{4}{1}\binom{5}{2}3!$$ ways, so the probability that each child receives at least one game is $$\frac{\binom{4}{1}\binom{5}{2}3!}{4^5}$$

Answer 2

Let us denote $[n]:=\{1,2,\dots,n\}$ for any positive integer $n$ and $Y^X$ for the set of functions $X\to Y$ in the situation where $X$ and $Y$ are sets.

The question can be rephrased as:

"If $f$ is a randomly chosen element of $[4]^{[5]}$ then what is the probability that it is a surjection?"

A direct answer on that is: $$\frac{4!S(5,4)}{4^5}$$where $S(n,k)$ is used as a notation for Stirling number of the second kind.

Here the numerator equals the number of favorable outcomes (surjections $[5]\to[4]$) and the denominator equals the number of possible outcomes (functions $[5]\to[4]$).

Answer 3

The inclusion-exclusion principle seems the simplest here.

P(each child gets at least one game)

$= \dfrac{4^5- \binom41 3^5 + \binom42 2^5 - \binom43 1^5}{4^5} = \dfrac{15}{64}$

Of course, as drhab says, inclusion-exclusion is involved in Stirlng numbers of the second kind, and using it gives the answer in a jiffy if you have recourse to its tables.