4
$\begingroup$

Count the number of solutions to the following:
$$x_1+x_2+\cdots+x_5=45$$
when: $1$. $x_1+x_2>0$, $x_2+x_3>0$, $x_3+x_4>0$

$2$. $x_1+x_2>0$, $x_2+x_3>0$, $x_4+x_5>1$

($x_1,\ldots,x_5$ are non-negative integers)
Thanks!

$\endgroup$
6
$\begingroup$

1) Divide five cases

$\bullet \quad x_1=0, x_2\ge 1, x_3=0, x_4\ge 1, x_5\ge 0$

then $\quad 0+x_2+0+x_4+(x_5+1)=46\quad $ number of solutions as $\displaystyle {45\choose 2}=990$

$\bullet \quad x_1=0, x_2\ge 1, x_3\ge 1, x_4\ge 0, x_5\ge 0$

then $\quad 0+x_2+x_3+(x_4+1)+(x_5+1)=47\quad $ number of solutions as $\displaystyle {46\choose 3}=15180$

$\bullet \quad x_1\ge 1, x_2=0, x_3\ge 1, x_4\ge 0, x_5\ge 0$

then $\quad x_1+0+x_3+(x_4+1)+(x_5+1)=47\quad $ number of solutions as $\displaystyle {46\choose 3}=15180$

$\bullet \quad x_1\ge 1, x_2\ge 1, x_3= 0, x_4\ge 1, x_5\ge 0$

then $\quad x_1+x_2+0+x_4+(x_5+1)=46\quad $ number of solutions as $\displaystyle {45\choose 3}=14190$

$\bullet \quad x_1\ge 1, x_2\ge 1, x_3\ge 1, x_4\ge 0, x_5\ge 0$

then $\quad x_1+x_2+x_3+(x_4+1)+(x_5+1)=47\quad $ number of solutions as $\displaystyle {46\choose 4}=163185$

Result: $990+15180+15180+14190+163185=\boxed{208725}$

2) Similar

$\endgroup$
2
$\begingroup$

Using the principle of inclusion-exclusion, we can derive the required generating function and extract the coefficient for the formula.

1)

Let $\mathbb{N}$ indicate the number of solutions with the only condition being that any $x_i\ge 0$.

Let the given constraints be:

$A: x_1+x_2>0\\ B: x_2+x_3>0\\ C: x_3+x_4>0 $

We require the number of solutions with all the above constraints, indicated by $N\left({A\cap B\cap C}\right)$

which can also be written as \begin{align} N\left({A\cap B\cap C}\right)&=\mathbb{N}-N\left(\overline{A\cap B\cap C}\right) \tag 1\\ &=\mathbb{N}-N\left(\overline A\cup \overline B\cup \overline C\right) \end{align}

The overlines are just compliments of the constraints, e.g. $\overline A : x_1+x_2=0$ etc.

Also, by PIE

$$ N\left(\overline A\cup \overline B\cup \overline C\right)=N(\overline A)+N(\overline B)+N(\overline C)-N(\overline A \cap \overline B) -N(\overline A \cap \overline C)-N(\overline B \cap \overline C)+N(\overline A\cap \overline B\cap \overline C) \tag 2 $$

In the above formulas, the condition for other $x_i\ge 0$ holds good simultaneously.

We can then easily write down the g.f. for $(2)$

\begin{align} g(x)&=\frac{1}{(1-x)^3}+\frac{1}{(1-x)^3}+\frac{1}{(1-x)^3}-\frac{1}{(1-x)^2}-\frac{1}{(1-x)}-\frac{1}{(1-x)^2}+\frac{1}{(1-x)}\\ &=\frac{3}{(1-x)^3}-\frac{2}{(1-x)^2} \end{align}

Hence, the g.f. for $(1)$ is:

\begin{align} G_1(x)&=\frac{1}{(1-x)^5}-\frac{3}{(1-x)^3}+\frac{2}{(1-x)^2} \end{align}

Hence, the general formula for the number of solutions is:

\begin{align} a_n&=\binom{n+4}{4}-3\,\binom{n+2}{2}+2\, \binom{n+1}{1}\\ \therefore a_{45}&=\boxed{208725} \end{align}

2)

This also can be done similarly, but need to be more careful with the constraints.

We will end up with the following generating function:

\begin{align} G_2(x)&=\frac{1}{(1-x)^5}-\frac{3+2\, x}{(1-x)^3}+\frac{1}{(1-x)^2}+\frac{2\, (1+2\, x)}{(1-x)}-(1+2\, x) \end{align}

and

\begin{align} b_n&=\binom{n+4}{4}-3\, \binom{n+2}{2}-2\, \binom{n+1}{2}+\binom{n+1}{1}+6\\ \therefore b_{45}&=\boxed{206615} \end{align}

$\endgroup$
0
$\begingroup$

Not very elegant, but the symmetry cuts down the checking a lot.

In (1), the restrictions are that $x_1$ or $x_2$ are nonzero, and so on. As there are no further restrictions, this divides into $x_1 \ne 0$ and $x_2 = 0$ or viceversa (essentially one variable less) or $x_1 \ne 0$ and $x_2 \ne 0$. Same for the others.

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