4
$\begingroup$

Find the number of solutions of the equation $x_1+x_2+x_3+x_4=15$ where variables are constrained as follows:

(a) Each $x_i \geq 2.$

(b) $1 \leq x_1 \leq 3$ , $0 \leq x_2$ , $3 \leq x_3 \leq 5$, $2 \leq x_4 \leq 6$

I believe I understand part A. I can fix the values at greater than two by adding two to each term, as in:

$(x_1 + 2) + (x_2 + 2) + (x_3+2) +(x_4+2) = 15$

$x_1+x_2+x_3+x_4=7$

So, $C(7+4-1,7) = {10! \over 7!3!} = 120$

For part B, i really have no idea where to start. Thanks for any insight!

$\endgroup$
2
$\begingroup$

Assume $a$ as a real number, such that $0<a <1$
The number of integral solutions should be the same as:

The coefficient of $a ^ {15}$ in $ \left(a + a^{2} + a^{3} \right)\left(1+a + a^{2} + a^{3} + ... \right)\left(a^{3} + a^{4} + a^{5} \right)\left(a^{2} + a^{3} + a^{4} +a^{5} + a^{6}\right) $

This is same as the coefficient of $a ^ {9}$ in $ \left(1 + a + a^{2} \right)^{2}\left(1+a + a^{2} + a^{3} + ... \right)\left(1+a+a^{2} + a^{3} + a^{4}\right) $

This is same as the coefficient of $a ^ {9}$ in
$ \left(1 -a^{3} \right)^{2}\left(1-a^{5}\right)\left(1-a\right)^{-4} $

Which is same as the coefficient of $a ^ {9}$ in
$ \left(1 -2a^{3} + a^6 \right)\left(1-a^{5}\right)\left(1+4a+\frac{4.5}{2!}a^2+\frac{4.5.6}{3!}a^3+\frac{4.5.6.7}{4!}a^4+...\right) $

Which is same as the coefficient of $a ^ {9}$ in
$ \left(1 -2a^{3} + a^6 - a^5+ 2 a^8 \right)\left(1+4a+\frac{4.5}{2!}a^2+\frac{4.5.6}{3!}a^3+\frac{4.5.6.7}{4!}a^4+...\right) $

Which is
$\binom{12}{3} - 2\binom{9}{3} + \binom{6}{3} - \binom{7}{3} + 2\binom{4}{3} = 45$

$\endgroup$
1
  • 1
    $\begingroup$ Nice work. But in the last two lines perhaps you have gone for the coefficient of $a^6$ instead of $a^9$? E.g. I think the first factor in the 2nd last line should be $(1-2a^3-a^5+a^6+2a^8)$ instead of $(1-2a^3-a^5+a^6)$. $\endgroup$
    – Mick A
    Dec 5 '14 at 10:05
1
$\begingroup$

By similar reasoning to (a) we can simplify the problem to:

\begin{eqnarray*} x_1+x_2+x_3+x_4 &=& 9 \qquad\qquad\text{(*)} \\ \text{with } && 0 \leq x_1 \leq 2 \\ && 0 \leq x_2 \\ && 0 \leq x_3 \leq 2 \\ && 0 \leq x_4 \leq 4. \end{eqnarray*}

Define sets \begin{eqnarray*} S\;\, &=& \{\text{all solutions to (*) without upper bounds on the $x_i$}\} \\ S_1 &=& \{\text{all solutions in $S$ where $x_1 \geq 3$}\} \\ S_2 &=& \{\text{all solutions in $S$ where $x_3 \geq 3$}\} \\ S_3 &=& \{\text{all solutions in $S$ where $x_4 \geq 5$}\} \\ \end{eqnarray*}

By the same method used in (a) we calculate:

\begin{eqnarray*} |S| &=& \binom{9+4-1}{9} = \binom{12}{9} \\ |S_1| = |S_2| &=& \binom{6+4-1}{6} = \binom{9}{6} \\ |S_3| &=& \binom{4+4-1}{4} = \binom{7}{4} \\ |S_1 \cap S_2| &=& \binom{3+4-1}{3} = \binom{6}{3} \\ |S_1 \cap S_3| = |S_2 \cap S_3| &=& \binom{1+4-1}{1} = \binom{4}{1} \\ |S_1 \cap S_2 \cap S_3| &=& 0. \end{eqnarray*}

Then we require, where set complement is with respect to $S$,

\begin{eqnarray*} \text{Ans.} &=& |S_1^c \cap S_2^c \cap S_3^c| \\ &=& |S| - |S_1 \cup S_2 \cup S_3| \qquad\qquad\text{by de Morgan's Law} \\ &=& |S| - (|S_1| + |S_2| + |S_3|) + (|S_1 \cap S_2| + |S_1 \cap S_3| + |S_2 \cap S_3|) - |S_1 \cap S_2 \cap S_3| \\ &&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\text{by the Inclusion-Exclusion Principle} \\ &=& \binom{12}{9} - 2\binom{9}{6} - \binom{7}{4} + \binom{6}{3} + 2\binom{4}{1} - 0 \\ &=& 220 - 168 - 35 + 20 + 8 \\ &=& 45. \end{eqnarray*}

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