How many ways are there to give 20 different presents to 4 different children, so that no child gets exactly 6 presents. All presents are different.

Question

Prompt:

How many ways are there to give 20 different presents to 4 different children, so that no child gets exactly 6 presents. All presents are different.

Here's what I tried doing

Since there are 20 presents to be distributed among 4 children,

$$C_1 + C_2 + C_3 + C_4 = 20$$ By bars and stars, $$\binom{ 20 + 4-1 }{ 4-1 } = \binom{ 23 }{ 3 } = 1771$$

$C_2 + C_3 + C_4 = 14 $ (after giving 6 presents to $C_1$)

Assuming $C_1$ gets 6 present = $\binom{ 14 + 3 - 1 }{ 3 - 1 } = \binom{ 16 }{ 2 } = 120$

Assuming $C_2$ gets 6 presents = $\binom{ 14 + 3 - 1 }{ 3 - 1 } = \binom{ 16 }{ 2 } = 120$

Assuming $C_3$ gets 6 presents = $\binom{ 14 + 3 - 1 }{ 3 - 1 } = \binom{ 16 }{ 2 } = 120$

Assuming $C_4$ gets 6 presents = $\binom{ 14 + 3 - 1 }{ 3 - 1 } = \binom{ 16 }{ 2 } = 120$

No one gets exactly 6 presents = Total - Everyone gets 6 presents

= $\binom{ 23 }{ 3 } - \binom{ 4 }{ 1 }\binom{ 16 }{ 2 } = 1771 - 480 = 1291$

I am new to combinatorics and not sure if I'm on the right path any help would be appreciated.

Answer 1

Your use of combinations with repetition would be appropriate if the presents are identical. However, they are different, so it matters which child receives which present.

If there were no restrictions, there would be four possible recipients for each of the twenty presents, so there would be $4^{20}$ ways to distribute the presents to the children.

From these, we must exclude those distributions in which one or more children receive exactly six presents. Since $4 \cdot 6 = 24 > 20$, at most three of the children can receive exactly six presents.

There are $\binom{4}{1}$ ways to select a child who will receive six presents and $\binom{20}{6}$ ways to select the presents that child receives. The remaining $20 - 6 = 14$ presents can be distributed among the remaining three children in $3^{14}$ ways. Hence, there are $$\binom{4}{1}\binom{20}{6}3^{14}$$ distributions in which a child receives exactly six presents.

There are $\binom{4}{2}$ ways to select two of the four children to receive exactly six presents. There are $\binom{20}{6}$ ways to select six of the presents for the younger of the two selected children and $\binom{20 - 6}{6} = \binom{14}{6}$ ways to select six presents for the older of the two selected children. The remaining $20 - 2 \cdot 6 = 8$ presents can be distributed to the remaining two children in $2^6$ ways. Hence, the number of distributions in which two children receive exactly six presents is $$\binom{4}{2}\binom{20}{6}\binom{14}{6}2^8$$

There are $\binom{4}{3}$ ways to select three of the four children to receive exactly six presents. There are $\binom{20}{6}$ to distribute six of the twenty presents to the youngest of the selected children, $\binom{14}{6}$ ways to distribute six of the fourteen remaining presents to the next youngest of the selected children, and $\binom{8}{6}$ ways to distribute six of the remaining eight presents to the oldest of the selected children. There is one way to distribute the remaining $20 - 3 \cdot 6 = 2$ presents to the other child. Hence, the number of distributions in which three of the children receive exactly six presents is $$\binom{4}{3}\binom{20}{6}\binom{14}{6}\binom{8}{6}1^2$$

By the Inclusion-Exclusion Principle, the number of distributions in which no child receives exactly six of the twenty presents is $$4^{20} - \binom{4}{1}\binom{20}{6}3^{14} + \binom{4}{2}\binom{20}{6}\binom{14}{6}2^{8} - \binom{4}{3}\binom{20}{6}\binom{14}{6}\binom{8}{6}1^2$$

Answer 2

The presents are different so the stars and bars formula doesn't work here. For example, the number of ways to distribute $20$ different presents to $4$ children is $4^{20}$ since each present can go to $4$ possible children (think of stamping the name of the child on each present).

Let $U$ be the set of all distributions of the $20$ different presents without constraints and let $A_i$ be the set of distributions in which child $i$ has exactly 6 presents. Then by PIE, the desired quantity equals $$ |\bar{A}_1\cap\bar{ A}_2\cap \bar{A}_3\cap \bar{A}_4|=|U|-S_1+S_2-S_3+S_4\tag{1} $$ where $$ S_k=\sum_{1\leq i_1<\dotsb<i_k\leq 4}|A_{i_1}\cap\dotsb A_{i_k}|.\tag{2} $$ From the above discussion $|U|=4^{20}$ and clearly, $$S_4=|A_1\cap\dotsb \cap A_4|=0.\tag{3}$$

To find $S_1$ note that $|A_i|=\binom{20}{6}3^{14}$ for all $i$ since we choose which six of the $20$ presents child $i$ gets and we distribute the remaining $14$ presents among the remaining $3$ children. Hence $$ S_1=\binom{4}{1}\times\binom{20}{6}3^{14}\tag{4}. $$ To find $S_2$ note that for $i\neq j$, we have that $|A_i\cap A_j|=\binom{20}{6}\binom{14}{6}2^{8}$ since we distribute $6$ presents to each of $i$ and $j$ and then the remaining $8$ are distributed without constraints. Hence $$ S_2=\binom{4}{2}\times\binom{20}{6}\binom{14}{6}2^{8}.\tag{5} $$ Finally, using similar reasoning as above $$ S_3=\binom{4}{3}\times\binom{20}{6}\binom{14}{6}\binom{8}{6}1^{2}.\tag{6} $$ Thus, by (1) $$ \text{number of ways}=4^{20}-\binom{4}{1}\binom{20}{6}3^{14}+\binom{4}{2}\binom{20}{6}\binom{14}{6}2^{8}-\binom{4}{3}\binom{20}{6}\binom{14}{6}\binom{8}{6}1^{2}+0. $$

Answer 3

For future reference here is a verification of the result by N.F. Taussig, which I upvoted. This is the case where it is possible for a child not to receive any presents. The combinatorial species here is

$$\mathfrak{S}_{=4}(\mathfrak{P}_{\ne 6}(\mathcal{Z})).$$

We get the generating function

$$G(z) = \left(\exp(z)-\frac{z^6}{6!}\right)^4 \\ = \exp(4z) - 4\frac{\exp(3z)z^6}{6!} + 6\frac{\exp(2z)z^{12}}{6!^2} - 4\frac{\exp(z)z^{18}}{6!^3} + \frac{z^{24}}{6!^4}.$$

Extracting coefficients we find

$$20! [z^{20}] G(z) = 20! \left(\frac{4^{20}}{20!} - 4 \frac{3^{14}}{14! \times 6!} + 6 \frac{2^8}{8!\times 6!^2} - 4\frac{1^2}{2!\times 6!^3}\right).$$

This evaluates to

$$\bbox[5px,border:2px solid #00A000]{523708416736.}$$