Deriving a formula for the number of nonnegative integer solutions to the equation $x_1+x_2+x_3+x_4+x_5+x_6+x_7+x_8=n$

98 Views Asked by At

Let $c_n$ denote the number of integer solutions $\left(x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8\right)$ to $$ x_1+x_2+x_3+x_4+x_5+x_6+x_7+x_8=n, $$ with each $x_i \geq 0$.
(i) Derive a formula for $c_n$ via a combinatorial argument.

Answer: Using the stars and bars technique $$*|*|*|*|* |* |* |*$$

Using 8 bins to distribute n distinct balls the answer would be $c_n$ = $\binom{n-1}{7}$ based on the formula $\binom{n-1}{r-1}$

is this the correct approach?

2

There are 2 best solutions below

0
On

The equation $$ x_1+x_2+x_3+x_4+x_5+x_6+x_7+x_8=n, $$ with each $x_i \geq 0$, can be put into the usual stars and bars form by considering $y_i = x_i + 1$. Then adding $8$ to both sides we get the equivalent equation $$ y_1+y_2+y_3+y_4+y_5+y_6+y_7+y_8=n+8 $$ with each $y_i \geq 1$. Hence the number of solutions is $$ \binom{n+8-1}{8-1} $$ since there are $n+8$ identical balls to distribute among $8$ distinct bins with no bin empty.

0
On

$$ x_1+x_2+x_3+x_4+x_5+x_6+x_7+x_8=n, $$ with each $x_i \geq 0$.

It is wrong, because your solution only works if all $x_i>0$, for exmaple, let $n=8$, then your answer gives $1$, which means only one solution. But in fact, at least we have $8+0+...+0+0=8,~~~~~ 0+8+...+0+0=8,~~~~~ ...,~~~~~ 0+0+...+0+8=8$