To find the number of ways to put $14$ identical balls into $4$ bins with the condition that no bin can hold more than $7$ balls.

Question

To find the number of ways to put $14$ identical balls into $4$ bins with the condition that no bin can hold more than $7$ balls.

---

I have tried the following:

The total no of ways to distribute $14$ identical balls into $4$ bins without any restriction is $$\binom{14+4-1}{4-1}= \binom{17}{3}.$$

Note that there can't be two bins with more than $7$ balls since we have only $14$ identical balls only.

Now, we count the no. of ways so that one bin has more than $7$ balls. So, it has at least $8$ balls and the remaining $6$ can be distributed in $\binom{6+4-1}{4-1}= \binom{9}{3}$ ways. We can choose one bin out of $4$ in $4$ ways.

Hence the reqd number of ways = $$\binom{17}{3} - 4 \times \binom{9}{3}.$$

Answer 1

What you have is correct. Here’s a slightly alternative approach. You want to count the nonnegative integer solutions to $x_1+x_2+x_3+x_4=14$ such that $x_i\le 7$ for all $i$. By inclusion-exclusion and stars-and-bars, we have $$\binom{14+4-1}{4-1}-\binom{4}{1}\sum_{k=8}^{14}\binom{14-k+3-1}{3-1}$$ solutions. By the hockey-stick identity, the sum reduces to $\binom{9}{3}$ as in your answer.

Answer 2

Your required sum is the coefficient of $x^{14}$ in

$$(1+x+\dots+x^7)^4$$

or

$$[x^{14}]:\left(\frac{1-x^8}{1-x}\right)^4$$

We can expand $(1-x^8)^4$ into $1-4x^8$, and the other term is $\sum_{i=0}^\infty \binom{i+3}{3}x^i$.

We want the values only when $i=6$ or $i=14$, which gives your equation.