6
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ I reformatted the formulas in your post. See math notation guide. $\endgroup$ – user147263 Aug 21 '14 at 5:08
  • $\begingroup$ I think you can use generating functions to solve this problem. $\endgroup$ – Bumblebee Aug 21 '14 at 6:49
  • $\begingroup$ the solution is given in this other post $\endgroup$ – G Cab Aug 1 '17 at 21:58
4
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ A bit more explanation of the multinomial approach would be useful. It is difficult to see how it follows. For example, expanding $(1-x)^{-4}$ $\endgroup$ – robjohn Aug 21 '14 at 7:22
6
$\begingroup$

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}$.

$\endgroup$
1
$\begingroup$

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 $$

$\endgroup$
  • $\begingroup$ @robjohn, nice to know. You did it to me a few times already ;-) $\endgroup$ – vonbrand Aug 12 '15 at 20:26
  • $\begingroup$ There are a few points however. $\left(1-z^7\right)^4=1-4z^7+6z^{14}-4z^{21}+z^{28}$ (the signs change). Also, $\binom{k+3}{k}=\binom{k+3}{3}$ only when $k\ge0$. If $k\lt0$ they are not $\endgroup$ – robjohn Aug 12 '15 at 20:33
  • $\begingroup$ @robjohn, doh... Fixing... $\endgroup$ – vonbrand Aug 12 '15 at 20:45
  • $\begingroup$ When $n=14$, the last two terms do not vanish: $\binom{-4}{3}=-\binom{6}{3}$ and $\binom{-11}{3}=-\binom{13}{3}$. The ones that do vanish are $\binom{-4}{-7}$ and $\binom{-11}{-14}$. $\endgroup$ – robjohn Aug 12 '15 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.