Find the number of ways to fill $4$ different boxes with $14$ balls if the last box must not have more balls than the sum of the first three boxes

Question

From this question,

Find the number of ways to fill the same $14$ balls into $4$ different boxes, but the last box must not have more than the sum of number of balls in the first three boxes.

I have done these following steps and I'm lost. Can you help me solve?

$x_1$ $+$ $x_2$ $+$ $x_3$ $+$ $x_4$ $=$ $14$ and $x_4$ $\geq$ $x_1$ $+$ $x_2$ $+$ $x_3$ So, $f(x)$ $=$ $($ $1$ $+$ $x$ $+$ $x^2$ $+$ $...$ $)$ $^3$ $\cdot$ $?$

Answer 1

You might want to try something like this:

$$f(x, y) = (1 + x + x^2 + ... + x^{14})^3 (1 + y + y^2 + ... + y^{14})$$

Where $x$ is the dummy variable for the first 3 boxes and $y$ is for the last. Since the two parts are just partial sums of the geometric series, f(x,y) is equal to:

$$\left(\frac{1-x^{15}}{1-x}\right)^3 \frac{1-y^{15}}{1-y}$$

We can simplify the left term using the binomial expansion:

$$ (1-x^{15})^{3} = \sum_{k=0}^{3} {3 \choose k} 1^k (-x^{15})^{3-k} = -x^{45} + 3x^{30} - 3x^{15} + 1$$

Reciprocating the denominator and using the negative binomial expansion, we get:

$$(1-x)^{-3} = \sum_{k=0}^{\infty} (-1)^k {3+ k - 1 \choose k} (-x)^k 1^{-3-k} = \sum_{k=0}^{\infty} {3+ k - 1 \choose k} x^k = 1 + 3x + ... + {16 \choose 14} x^{14} + ...$$

You don't care about powers higher than 14 because there are only 14 balls. This means the left term is:

$$(1-x^{15})^{3} (1-x)^{-3} = (-x^{45} + 3x^{30} - 3x^{15} + 1)( 1 + 3x + ... + {16 \choose 14} x^{14} + ...)$$

Now just do the same for the $y$ terms, multiply the two results together and add up the coefficients where the power of y is less than or equal to the power of x.

Answer 2

The most straightforward way to get a single generating function here is to use complementary counting:

1. First, find $F(x)$, the generating function for splitting balls into 4 boxes. This should be easy.
2. Second, find $G(x)$, the generating function for splitting balls into 4 boxes where the last box contains more than the other three.
3. Finally, if $H(x) = F(x) - G(x)$, then $[x^{14}]H(x)$, the coefficient of $x^{14}$ in $H(x)$, should be the number of ways to put 14 balls into 4 boxes where the last box contains at most as many as the other three.

---

The first step, finding $F(x)$, is a straightforward conversion from balls-and-boxes type problems into generating functions. For each box, we have a factor of $$\frac1{1-x} = 1 + x + x^2 + x^3 + \dotsb$$ representing the number of balls that could be in it; we multiply these together because we choose the balls in each box separately, and get $$F(x) = \frac1{(1-x)^4}.$$

---

For the second step, we need to do a change of variables. Rather than choose $a, b, c, d$ (the number of balls in each box) with the condition that $a \ge 0, b \ge 0, c \ge 0, d > a+b+c$, we will define $d' = d - a - b - c$ and choose $a \ge 0, b \ge 0, c \ge 0, d' \ge 1$.

This changes how we compute the total number of balls: it's no longer $a+b+c+d$ but $2a + 2b + 2c + d'$. So an increase in each of $a, b, c$ contributes $2$ to the total, and therefore the choices for $a, b, c$ are represented by $$\frac1{1-x^2} = 1 + x^2 + x^4 + x^6 + \dotsb.$$ Meanwhile, an increase in $d'$ contributes $1$ to the total, but $d'$ cannot be $0$, so the choices for $d'$ are represented by $$\frac x{1-x} = x + x^2 + x^3 + x^4 + \dotsb.$$ Overall, we get $$G(x) = \left( \frac1{1-x^2}\right)^3 \left(\frac{x}{1-x}\right) = \frac{x}{(1-x^2)^3 (1-x)}.$$

---

Finally, we take the difference and get $$H(x) = \frac1{(1-x)^4} - \frac{x}{(1-x^2)^3(1-x)}.$$ The coefficient of $x^{14}$ here is the final answer.