# Stars and bars (combinatorics) with multiple bounds

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!

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

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}

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.