Dividing balls into boxes with capacity limits

Question

Problem:

In how many ways can you divide $13$ identical balls into $3$ different boxes $k_1$, $k_2$, $k_3$, such that $k_1$ contains no more than $5$ balls, $k_2$ contains no more than $6$ balls and $k_3$ contains no more than $4$ balls?

My idea:

So my idea is to use the following theorem: "There are $C(n+r-1,r)$ r-combinations from a set with $n$ elements when repetition of elements is allowed." But I'm not sure.

Any great hints would be appreciated.

Answer 1

The answer can simply be given using generating functions. We simply need to calculate the coefficient of $x^{13}$in the expansion of $$(1+x+x^2+x^3+x^4)(1+x+x^2+x^3+x^4+x^5)(1+x+x^2+x^3+x^6)$$ $$=\frac {(1-x^5)}{(1-x)}\cdot \frac {(1-x^6)}{(1-x)}\cdot \frac {(1-x^7)}{(1-x)}$$

$$=\frac {1-x^5-x^6-x^7+x^{11}+x^{13}+x^{12}-x^{18}}{(1-x)^3}$$

Hence the answer simply goes as $$\binom {15}{13} -\binom {10}{8}- \binom {9}{7}-\binom {8}{6}+\binom {4}{2}+1+\binom {3}{1}=6$$

Answer 2

$\mathbf {\text {Method 2 (Must see)} }$

Define $k_1=5-a$ , $k_2=6-b$ and $k_3=4-c$

Hence we get $$a+b+c=2$$ And we need non negative integral solutions of this equation which are $$\binom {4}{2}=6$$

Luckily this preserves non negativity of $k_1$,$k_2$ and $k_3$

Answer 3

To show the working behind the generating function approach:

A binomial expansion of $(1-x)^{-n}$ gives $$(1-x)^{-n} = 1 + (-n)(-x) + \frac{(-n)(-n-1)}{2!} (-n)^2 + \frac{(-n)(-n-1)(-n-2)}{3!} (-n)^3 + \cdots \\ = \sum_{i\ge 0}\frac{(-1)^i (-n)^\underline{i}}{i!}x^i \\ = \sum_{i\ge 0}\frac{n^\overline{\,i\,}}{i!}x^i \\ = \sum_{i \ge 0}\binom{n+i-1}{i}x^i \\ = \sum_{i \ge 0}\binom{n+i-1}{n-1}x^i$$

Then $$[x^k] \frac{\sum_{j\ge 0} a_j x^j}{(1-x)^n} = \sum_{j\ge 0} [x^k] \frac{a_j x^j}{(1-x)^n} = \sum_{j\ge 0} a_j [x^{k-j}] (1-x)^{-n} = \sum_{j\ge 0} a_j \binom{n+k-j-1}{n-1}$$

---

Now we can apply that to your problem as outlined in Manthanein's first answer: by considering the three boxes we're looking for the coefficient of $x^{13}$ in $$\frac {(1-x^6)(1-x^7)(1-x^5)}{(1-x)^3} = \frac{1-x^5-x^6-x^7+x^{11}+x^{12}+x^{13}-x^{18}}{(1-x)^3}$$

So applying the lemma with $n=3$, $k=13$ we get $$\binom{15-0}{2}-\binom{15-5}{2}-\binom{15-6}{2}-\cdots-\binom{15-18}{2}$$ The last term is zero, and the rest give $$\frac{15\times14 - 10\times9 -9\times8 - 8\times7 + 4\times3 + 3\times2 + 2\times1}{2}\\ = \frac{210-90-72-56+12+6+2}{2} = 6$$