In how many ways can we distribute $20$ balls into $5$ boxes?

Question

In how many ways can we put $20$ balls into $5$ boxes A, B, C, D, E so that A has at most $3$ balls and B at most $2$ balls?

$$$$

If we had at least instead of at most we would put the minimum number of balls into these boxes and distribute the remaining balls into the 5 boxes. But what do we have to do now where we have at most ?

Answer 1

If these are indistinguishable balls then you can use the generating function $$\frac{(1+x+x^2+x^3)(1+x+x^2)}{(1-x)^3}$$ and look at the coefficient of $x^{20}$ in the expansion, which is $${22 \choose 2}+2{21 \choose 2}+3{20 \choose 2}+3{19 \choose 2}+2{18 \choose 2}+{17 \choose 2} = 2176$$

Answer 2

Hint

You can solve

$$a+b+c+d+e=20$$

such that $a\le 3$ and $b\le 2$, so $a+b\le 5\to a+b\in\{0,1,2,3,4,5\}$. Solve for each case and you will see the pattern.

Answer 3

Into box $B_1:=A$ we can put $0$, $1$, $2$, or $3$ balls. If putting $k$ balls into a box is "worth" $x^k$ then the sum of the options for box $B_1$ is $$1+x+x^2+x^3={1-x^4\over 1-x}\ .\tag{1}$$ Similarly the sum of the options for box $B_2:=B$ is $$1+x+x^2={1-x^3\over 1-x}\ .\tag{2}$$ For each of the three remaining boxes $B_j$ the sum of the options is $$1+x+x^2+\ldots={1\over1-x}\qquad(3\leq j\leq 5)\ ,\tag{3}$$ whereby for the moment we don't care that there are just $20$ balls available. If we multiply the five sums in $(1)$–$(3)$we obtain $${(1-x^4)(1-x^3)\over(1-x)^5}=(1-x^3-x^4+x^7)\sum_{k=0}^\infty{4+k\choose k}x^k\ .\tag{4}$$ The rationale behind taking this product is the following: If we would multiply the sums on the LHSs of $(1)$–$(3)$ distributively we would obtain for each choice of options that consumes $N$ balls in total a term $x^N$. Collecting all these terms produces $ax^N$, whereby the resulting coefficient $a\in{\mathbb N}_{\geq0}$ gives the number of allocations where exactly $N$ balls have been used. It follows that we should find the coefficient of $x^{20}$ on the RHS of $(4)$.This coefficient is $${24\choose20}-{21\choose17}-{20\choose16}+{17\choose13}=2176\ .$$ In hindsight we can interpret the obtained sum $${24\choose4}-{21\choose4}-{20\choose4}+{17\choose4}$$ as result of an inclusion/exclusion process: From the number ${24\choose4}$ of all possible allocations deduct the number of allocations where $B$ has obtained $3$ balls "for free" in advance as well as the number of allocations where $A$ has obtained $4$ balls in advance. In this way we have counted the cases where both $A$ and $B$ have obtained their advances twice; therefore we have to throw these allocations into the sum again.