5
$\begingroup$

How many solutions are there to the equation

$x_1 + x_2 + x_3 + x_4 + x_5 = 21$

where $x_1, i = 1,2,3,4,5$ is a nonnegative integer such that $0 ≤ x_1 ≤ 3, 1 ≤ x_2 < 4$, and $x_3 ≥ 15$?

I have correctly completed the previous parts of the question but am having trouble with this particular restriction.

The total number of solutions to the equation is $C(25,21) = 12650$.

I have tried to do each restriction individually:

For $0 ≤ x_1 ≤ 3$, I solved this by subtracting the number of solutions when $x_1 ≥ 4$ from the total number of solutions. This is $C(25,21) - C(21,17) = 5985$.

For $1 ≤ x_2 < 4$, I have $C(24,20) - C(21,17) = 5985$.

For $x_3 ≥ 15$, I have $C(10,6) = 210$.

However, the restriction is when these are all together. I am not sure how to proceed. The answer is $106$.

$\endgroup$
  • 1
    $\begingroup$ The $x_3\geq 15$ constraint is easier to handle than you might think. Just say you're looking for solutions to $x_1+x_2+x_3'+15+x_4+x_5=21$ instead, and $x_3'$ will have no explicit restrictions. For the two others, maybe inclusion-exclusion? $\endgroup$ – Arthur Aug 3 '16 at 1:39
  • $\begingroup$ @Arthur That's what I've done for $x_3 ≥ 15$. I figured I might have to do some inclusion-exclusion stuff but I'm not sure how here. $\endgroup$ – userrandomnums Aug 3 '16 at 2:22
2
$\begingroup$

The system:

$\begin{cases} x_1+x_2+x_3+x_4+x_5=21\\ 0\leq x_1\leq 3\\ 1\leq x_2<4\\ 15\leq x_3\\ 0\leq x_4\\ 0\leq x_5\end{cases}$

can be rewritten via a change of variables as:

$\begin{cases} y_1+y_2+y_3+y_4+y_5=5\\ 0\leq y_1\color{blue}{\leq 3}\\ 0\leq y_2\color{blue}{\leq 2}\\ 0\leq y_3\\ 0\leq y_4\\ 0\leq y_5\end{cases}$

Do you see how?

Let $x_1=y_1, x_2=y_2+1, x_3=y_3+15$ and $x_4=y_4$ and $x_5=y_5$. Each of the conditions translate directly as above, including $y_1+y_2+y_3+y_4+y_5=x_1+x_2-1+x_3-15+x_4+x_5=21-1-15=5$

Now, approach via inclusion-exclusion on the first two terms. If we were to ignore the upper bounds, how many solutions are there?

$\binom{5+5-1}{5-1}=\binom{9}{4}$

How many of those solutions violate the first upper bound condition?

that would be when $y_1>3$ i.e. $4\leq y_1$. Making another change of variable, this would be $z_1+z_2+\dots+z_5=1, 0\leq z_i$ for a total of $\binom{5}{4}=5$

How many of them violated the second upper bound condition?

Approach similarly

How many violate both upper bound conditions simultaneously?

That would be with $x_1\geq 4, x_2\geq 4, x_3\geq 15$ implying that $x_1+x_2+x_3+x_4+x_5\geq x_1+x_2+x_3\geq 23$ and couldn't equal $21$, so none violate both.

Letting $|S|$ be the amount which ignore both upper bound conditions, $|A_1|$ be the amount which violate the first upper bound condition, $|A_2|$ be the amount which violate the second upper bound condition, we have the number of solutions which violate none of the upper bound conditions as:

$$|S|-|A_1|-|A_2|+|A_1\cap A_2|$$

$126 - 5 - 15 + 0 = 106$

$\endgroup$
  • $\begingroup$ Shouldn't the equation with y_2 be 0<= y_2 <= THREE instead? I would propose an edit, but am not quite sure how it affects the rest of JMoravitz's answer. $\endgroup$ – nickalh Aug 3 '16 at 5:56
  • $\begingroup$ @nickalh no it should not. Notice that the original was $1\leq x_2 \color{red}{<}4$ which in the integers is equivalent to $1\leq x_2 \leq 3$ since there are no integers strictly between $3$ and $4$. Setting $y_2=x_2-1$ we have $0\leq y_2\leq 2$ or equivalently worded $0\leq y_2 < 3$. $\endgroup$ – JMoravitz Aug 3 '16 at 6:18
2
$\begingroup$

However, the restriction is when these are all together. I am not sure how to proceed.

Utilise the Principle of Inclusion and Exclusion and the Twelve Fold Way's "Stars and Bars" technique.

The total number of natural number solutions is: $\binom{21+5-1}{21}$.   This is the count of ways to place $21$ balls into $5$ boxes.   The "boxes" are the variables, and the value is incremented by $+1$ for each "ball"; so "five balls in box 1" corresponds to the event $\{x_1=5\}$.   You grok that okay?

Let us label the restrictions as $A:=\{0≤x_1 ≤3\}$, $B:=\{1≤x_2 <4\}$ and $C:=\{x_3 ≥15\}$

Now restriction $C$ alone is easy to count:   When at least $15$ balls must be placed in box three; we need only count the ways to distribute the remaining $6$ balls among all five boxes.

$$\lvert{C}\rvert=\binom{6+5-1}{6}$$

The other restrictions are more easily countable through their complements; though we'll split that for $B$ into two disjoint subsets (you'll see why soon).

Let $A'=\{x_2\geq 4\}, B'_1=\{x_2=0\}, B'_2=\{x_2\geq 4\}$

Then, noting that $B'_1\cap B'_2=\emptyset$, the Principle of Inclusion and Exclusion says "hello": $$\begin{align}\lvert{A\cap B\cap C}\rvert ~=~&\lvert{C}\rvert-\lvert{(A'\cup B_1'\cup B_2')\cap C}\rvert\\[1ex]~=~&\lvert{C}\rvert-\lvert{A'\cap C}\rvert-\lvert{B_1'\cap C}\rvert-\lvert{B_2'\cap C}\rvert+\lvert{A'\cap B_1'\cap C}\rvert+\lvert{A'\cap B_2'\cap C}\rvert\end{align}$$

To measure $\lvert{A'\cap C}\rvert$ : When at least $15$ balls are placed in box three and at least $4$ balls in box one; we must count the ways to distribute the remaining $2$ balls among all five boxes.

$$\lvert{A'\cap C}\rvert = \binom{2+5-1}{2}$$

To measure $\lvert{B_1'\cap C}\rvert$ : when $15$ are placed in box three and box two is kept empty; we must count the ways to distribute the remaining $6$ balls among the remaining four boxes.

$$\lvert{B'_1}\rvert = \binom{6+4-1}{6}$$

And so forth...

$\endgroup$
2
$\begingroup$

An approach using generating functions:

In order to count up the number of solutions that sum to $n$, we can look at the coefficient of $x^n$ in the generating function $f(x)$:

$$[x^{n}]f(x) = [x^{n}]\left(\sum_{n=0}^{3}x^n\right)\left(\sum_{n=1}^{3}x^n\right)\left(\sum_{n=15}^{\infty}x^n\right)\left(\sum_{n=0}^{\infty}x^n\right)\left(\sum_{n=0}^{\infty}x^n\right)$$

The $[x^n]$ operator refers to the coefficient of $x^n$.

Factor out $x$'s so you can shift the indices down to $n=0$ for each sum:

$$[x^{n}]f(x) = [x^{n}]\left(\sum_{n=0}^{3}x^n\right)x\left(\sum_{n=0}^{2}x^n\right)x^{15}\left(\sum_{n=0}^{\infty}x^n\right)\left(\sum_{n=0}^{\infty}x^n\right)\left(\sum_{n=0}^{\infty}x^n\right)$$

Use the identities $\displaystyle \sum_{n=0}^{\infty}x^n = \frac{1}{1-x}$ and $\displaystyle \sum_{n=0}^{k}x^n = \frac{1-x^{k+1}}{1-x}$ to convert each piece:

$$[x^{n}]f(x) = [x^{n}]\left(\frac{1-x^4}{1-x}\right)x\left(\frac{1-x^3}{1-x}\right)x^{15}\left(\frac{1}{1-x}\right)^3$$

Simplify:

$$[x^{n}]f(x) = [x^{n}]\left(\frac{x^{23}-x^{20}-x^{19}+x^{16}}{(1-x)^5}\right)$$

Factor out $\dfrac{1}{(1-x)^5}$ and use the identity $\displaystyle \frac{1}{(1-x)^{m+1}} = \sum_{n=0}^{\infty}\binom{n+m}{m}x^n$:

$$[x^{n}]f(x) = [x^{n}]\left(x^{23}-x^{20}-x^{19}+x^{16}\right)\sum_{n=0}^{\infty}\binom{n+4}{4}x^n$$

Distribute:

$$[x^{n}]f(x) = [x^{n}]\left(\sum_{n=0}^{\infty}\binom{n+4}{4}x^{n+23}-\sum_{n=0}^{\infty}\binom{n+4}{4}x^{n+20}-\sum_{n=0}^{\infty}\binom{n+4}{4}x^{n+19}+\sum_{n=0}^{\infty}\binom{n+4}{4}x^{n+16}\right)$$

Shift indices:

$$[x^{n}]f(x) = [x^{n}]\left(\sum_{n=23}^{\infty}\binom{n-19}{4}x^{n}-\sum_{n=20}^{\infty}\binom{n-16}{4}x^{n}-\sum_{n=19}^{\infty}\binom{n-15}{4}x^{n}+\sum_{n=16}^{\infty}\binom{n-12}{4}x^{n}\right)$$

If we look at the lower bounds of the indices, the smallest $x^n$ that we could get the coefficient for is $x^{16}$. This is because $16$ is the smallest possible value of $n$ under the $x_i$ constraints, which occurs when $x_1 = x_4 = x_5 = 0$, $x_2=1$, and $x_3=15$. The coefficients for all $n<16$ are simply $0$.

Now we can invoke the coefficient operator:

$$[x^n]f(x) = \binom{n-19}{4}-\binom{n-16}{4}-\binom{n-15}{4}+\binom{n-12}{4}$$

Set $n=21$ to get the number of solutions to the original problem:

$$[x^{21}]f(x) = 106$$

Side note: If you use $n<19$ in the expression above, you'll start to see negative binomial coefficients. For those, you need to use the identity $\binom{-n}{k} = (-1)^k\binom{n+k-1}{k}$

$\endgroup$
1
$\begingroup$

Let's compute it directly

let $y_3 = x_3-15$ and $y_2 = x_2-1$ and replace $x_2$ and $x_3$ in the main sum.

$x_1+y_2+x_3+x_4+y_5 = 21-1-15 = 5$

Now, let's apply the theorem 2 of stars and bars with $n = 5 , k = 5$ to compute the total of comb. including the not desired $x_1>=4$ and $x_2 >=4$ : $\tbinom{n + k - 1}{n}$ = $\tbinom{5 + 5 - 1}{5}$ = whole = $\tbinom{9}{5} = 126 $

Let's now apply $x_1 < 4$ and $y_2 < 3$

$x_1$ != 5 : only (5,0,0,0,0) , then 1 comb

$x_1$ != 4 : (4,?,?,?,?), then stars and bars again with $n=1 , k=4$ : $\tbinom 4 1 = 4$ comb

$y_2$ != 5 : only (0,5,0,0,0) , then 1 comb

$y_2$ != 4 : all the (?,4,?,?,?) , S&B with $n=1 , k=4$ : $\tbinom 4 1 = 4$ comb

$y_2$ != 3 : all the (?,3,?,?,?) , S&B with $n=2 , k=4$ : $\tbinom 5 1 = 10$ comb

then we get exclusions = $1 + 1 + 4 + 4 + 10 = 20 $ comb.

Result = whole - exclusions = $126 - 20 = 106$ combinations.

$\endgroup$

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.