Number of solutions of $x_1 + x_2 + x_3 + x_4 = 14$ such that $x_i \le 6$

Question

Let $x_1, x_2, x_3, x_4$ be nonnegative integers.

(a) Find the number of solutions to the following equation: $$ x_1 + x_2 + x_3 + x_4 = 14 $$

I got $17 \choose 3$ for this. Is that correct?

(b) Find the number of solutions if we add the restriction that $x_i \le 6$ for $1 \le i \le 4$

Answer 1

For part "a" it is correct.

For part "b":

Using Multinomial:

The ways are equivalent to: $$\text{ Coefficient of $x^{14}$ in }(x^0+x^1+x^2+...x^6)^4\\ =\text{ Coefficient of $x^{14}$ in }(1-x^7)^4(1-x)^{-4}\\ =\text{ Coefficient of $x^{14}$ in }\left(1-\binom41x^7+\binom42x^{14}-...\right)(1-x)^{-4}\\ =^*1\times\binom{4+14-1}{14}-\binom41\binom{4+7-1}{7}+\binom42\times1=206$$

Using the Inclusion–Exclusion Principle:

Let $p_i$ be the case such that p $x_i's$ are $\ge7$ Now: $$p_u=(p_1\cup p_2\cup p_3\cup p_4)=S_1-S_2+S_3-S_4$$ $$\begin{array}{|c|c|}\hline S_i&\text{values}\\\hline S_1&\binom41\left(\binom92+\binom82+\binom72+...\binom22\right)^{**}=480\\ S_2&\binom42\times1\times1=6\\ S_3&0\\ S_4&0\\\hline \end{array}$$ So,$p_u=480-6=474$, so that we get $680-474=206$ for b.

---

$^*$ Coefficient of $x^r$ in $(1-x)^{-n}$ is $\binom{n+r-1}r$

---

$^{**}$ Let $x_1$ be $k$ then $x_2+x_3+x_4=14-k$,ways for this are $\binom{16-k}2$

Total: $$\sum_{k=7}^{14}\binom{16-k}{2}=120$$

Answer 2

The answer you got for the first question is right.

For the second, call a distribution bad if one or more of the $x_i$ is $\ge 7$. Our strategy is to count the number of bads, and subtract from the answer of a).

One can have $2$ of the $x_i$ equal to $7$. This can be done in $\binom{4}{2}$ ways.

Now we count the number of bads in which only one of the $x_i$ is $\ge 7$. Which one it is can be chosen in $\binom{4}{1}$ ways. Suppose that $x_1\ge 7$. Give $7$ candies to kid 1. The remaining $7$ have to be split between the four people, with none of 2, 3, or 4 getting $7$. There are $\binom{10}{3}-3$ ways to do this.

We get a total of $\binom{4}{1}\left[\binom{10}{3}-3\right]+\binom{4}{2}$ bads.

Alternately, we use Inclusion/Exclusion more explicitly. Choose one of the $4$ to give at least $7$ to, and give her $7$. We can distribute the remaining $7$ among the $4$ people in $\binom{10}{3}$ ways. But this double-counts the $\binom{4}{2}$ ways to give $7$ to two of the variables. So the number of bads is $\binom{4}{1}\binom{10}{3}-\binom{4}{2}$.

Answer 3

Use generating functions. The ways to pick each $x_i$ is represented by:

$$ 1 + z + z^2 + z^3 + z^4 + z^5 + z^6 = \frac{1 - z^7}{1 - z} $$

Now you want four of those, and have them add up to $n$:

$\begin{align} [z^n] \frac{(1 - z^7)^4}{(1 - z)^4} &= [z^n] (1 - 4 z^7 + 6 z^{14} - 4 z^{21} + z^{28}) \cdot \sum_{k \ge 0} (-1)^k \binom{-4}{k} z^k \\ &= [z^n] (1 - 4 z^7 + 6 z^{14} - 4 z^{21} + z^{28}) \cdot \sum_{k \ge 0} \binom{k + 4 - 1}{4 - 1} z^k \\ &= \binom{n + 3}{3} - 4 \binom{n - 4}{3} + 6 \binom{n - 11}{3} - 4 \binom{n - 18}{3} + \binom{n - 25}{3} \\ \end{align}$

Here you have to be careful, the terms with negative upper index aren't present (no such terms are present in the sum, the first factor essentially picks out some of them). In the particular case $n = 14$:

$$ \binom{14 + 3}{3} - 4 \binom{14 - 4}{3} + 6 \binom{14 - 11}{3} = 206 $$