Presents for all!

I'll assume that each elf has a different present, so essentially we are looking for the probability that, when $7$ distinct presents are distributed at random to $4$ children, each child receives at least one present.

Now without restrictions the $7$ presents can be distributed in $4^{7} = 16384$ ways. To find the number of ways in which each child receives at least one present, I will first find the number of ways in which just $1, 2$ and $3$ children get all the presents, and then subtract the sum of these values from $4^{7}$ .

There are $4$ ways to distribute the presents so that all the presents go to one child.

There are $\binom{4}{2} * (2^{7} - 2) = 756$ ways in which all the presents can be distributed to just $2$ children. That is, we can choose $2$ of the children in $\binom{4}{2}$ ways, and then in each of these cases there are $2^{7}$ ways in which the presents can be distributed, $2$ of which would result in all the presents going to just one child, (hence the need to subtract $2$ from $2^{7}$ ).

There are $\binom{4}{3}*[3^{7} - 3 - \binom{3}{2}(2^{7} - 2)] = 7224$ ways in which all the presents can be distributed to just $3$ children. That is, we can choose $3$ of the children in $\binom{4}{3}$ ways, and then in each of these cases there are $3^{7}$ ways in which the presents can be distributed, $3$ of which would result in all the presents going to just one child, and $\binom{3}{2}(2^{7} - 2)$ of which would result in all the presents going to just two children, (where each of the two would receive at least one present).

Thus the number of ways in which the presents can be distributed so that each child gets at least one present is $16384 - 4 - 756 - 7224 = 8400$ .

The desired probability is then $\dfrac{8400}{16384} = \dfrac{525}{1024}$ .

Thus $A = 525, B = 1024$ and $B - A = \boxed{499}$ .

(Apologies for my long-winded explanation, but this problem is easy to mess up on so I felt the need to be as deliberate as possible.)

An easier way to solve the problem is to use the principle of inclusion and exclusion .

For this, let $A_i$ be the event that the $i$ th child does not receive any present, $i=1,2,3,4$ . We require the probability of the complement of the event $E=A_1\cup A_2\cup A_3 \cup A_4$ . We have, $\mathbb{P}( A_1\cup A_2\cup A_3 \cup A_4)=\sum_{i=1}^{4}\mathbb{P}(A_i)- \sum_{1\leq i<j\leq 4}\mathbb{P}(A_i\cap A_j)+ \\\sum_{1\leq i<j<k\leq 4}\mathbb{P}(A_i\cap A_j\cap A_k)- \mathbb{P}(A_1\cap A_2\cap A_3 \cap A_4)$ $=4 \big(\frac{3}{4}\big)^7-\binom{4}{2}\big(\frac{2}{4}\big)^7 + \binom{4}{3}\big(\frac{1}{4}\big)^7-0 = \frac{499}{1024}$ where each of the above probability terms should be self-explanatory. Thus the required probability is $1-\frac{499}{1024}=\frac{525}{1024}$ .

Say you are watching the elves come one-by-one, and are counting how many children have gifts after each one has come.

If there is currently 1 child with a present, then there is a $\frac{1}{4}$ chance that the next elf will give the present to that child, and a $\frac{3}{4}$ chance that the elf will give the present to a new child.

If there are currently 2 children with presents, then there is a $\frac{2}{4}$ chance that the next present will go to a child who already has a present, and a $\frac{2}{4}$ chance it will go to a new child.

Similarly, with 3 children, the chance of one of them receiving the next present is $\frac{3}{4}$ and the chance of the present going to the last child $\frac{1}{4}$ . If all 4 children have presents, then a new present will not change the number of children with presents.

We summarize these results in this matrix. $\begin{bmatrix} \frac{1}{4} & 0 & 0 & 0 \\ \frac{3}{4} & \frac{2}{4} & 0 & 0 \\ 0 & \frac{2}{4} & \frac{3}{4} & 0 \\ 0 & 0 & \frac{1}{4} & 1 \end{bmatrix}$ Now say we know the probabilities $p_n$ that $n$ children have a present at some point, $n=1,2,3,4$ . We can use the matrix to calculate the probabilities after the next elf by the following multiplication. $\begin{bmatrix} \frac{1}{4} & 0 & 0 & 0 \\ \frac{3}{4} & \frac{2}{4} & 0 & 0 \\ 0 & \frac{2}{4} & \frac{3}{4} & 0 \\ 0 & 0 & \frac{1}{4} & 1 \end{bmatrix}\begin{bmatrix} p_1 \\ p_2 \\ p_3 \\ p_4 \end{bmatrix}=\begin{bmatrix} \frac{1}{4}p_1 \\ \frac{3}{4}p_1 + \frac{2}{4}p_2 \\ \frac{2}{4}p_2 + \frac{3}{4}p_3 \\ \frac{1}{4}p_3 + p_4 \end{bmatrix}$ We know that after the first elf has come, exactly 1 child has a present. Therefore, the probability of $n$ children having a present after 6 more elves come is $\begin{bmatrix} \frac{1}{4} & 0 & 0 & 0 \\ \frac{3}{4} & \frac{2}{4} & 0 & 0 \\ 0 & \frac{2}{4} & \frac{3}{4} & 0 \\ 0 & 0 & \frac{1}{4} & 1 \end{bmatrix}^6\begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}=\begin{bmatrix} \frac{1}{4096} \\ \frac{189}{4096} \\ \frac{1806}{4096} \\ \frac{2100}{4096} \end{bmatrix}$ The probability of 4 children each having at least one present is $\dfrac{2100}{4096}=\dfrac{525}{1024}$ .

This gives $A=525$ , $B=1024$ , and $B-A=\boxed{499}$ .

Total number of distributions is 4^7

Now will use the concept of grouping

The possible number of gifts that can be distributed to each child such that each gets atleast one are

(4,1,1,1) (3,2,1,1)(2,2,2,1)

Using the grouping formula we can find the number of ways of grouping which will be 350.

Now these groups can be distributed among children is 24 ways.

So our answer is 24*350/4^7