# Is my solution correct? Generating functions question: How many non-negative solutions does the equation $x_1+x_2+x_3+x_4+x_5+x_6=12$ have?

so we began studying this subject, and I tried solving this question: How many non-negative and whole ($\in \Bbb Z$) solutions does the equation $x_1+x_2+x_3+x_4+x_5+x_6=12$ have?

I would like to know if my solution is correct.

For non negative solutions it means $0\leq x_1, x_2, x_3, x_4, x_5, x_6$, so I built the next function:

$A(x)=(1+x^1+x^2+x^3+...)^6$, and due to the formula of the sum of an infinite geometric sequence:

$A(x)= {1 \over (1-x)^6}= \sum_{n=0}^∞ {n+6-1 \choose 6-1}x^n$.

Since we need the sum of 12, we need the coefficient of $x^{12}$, so I place n=12, and got the number of solutions to be 6188.

Now this seemed a bit weird to me. Is it so?

Thanks for any input!

-
Why do you find this weird? Look OK to me. – Marc van Leeuwen May 20 '13 at 11:12

Your method of solving this is correct. It comes down basically to remembering the formula for the coefficients of $(1-x)^{-n}$. If you just call the coefficient of $x^k$ in that power series $(-1)^k\binom{-n}k$ (after all the coefficient of $x^k$ in $(1-x)^m$ is $(-1)^k\binom mk$ for $m\geq0$ too), then these new coefficients continue to satisfy $$\binom nk=\frac{n\times(n-1)\times\cdots\times(n-k+2)\times(n-k+1)} {k\times(k-1)\times\cdots2\times\times1} \qquad\text{for all n,}$$ and therefore in particular $$\binom {-n}k=\frac{-n\times(-n-1)\times\cdots\times(-n-k+2)\times(-n-k+1)} {k\times(k-1)\times\cdots2\times\times1} =(-1)^k\frac{n\times(n+1)\times\cdots\times(n+k-2)\times(n+k-1)} {k\times(k-1)\times\cdots2\times\times1} =(-1)^k\binom {k+n-1}k.$$ Therefore $(-1)^k\binom{-n}k=\binom {k+n-1}k=\binom {k+n-1}{n-1}$ which is (probably) your formula for the coefficients. (Be warned that although the first transformation is always valid, the symmetry of binomial coefficients used in the second step is only valid if the top index, here $k+n-1$, is non-negative! So there was no possibility if applying symmetry before the first transformation.)

What I'm saying is basically that you can remember the identity for all $n$ and for $k\in\mathbf N$ $\binom {-n}k=(-1)^k\binom {k+n-1}k$ (or if you prefer it in the form $\binom nk=(-1)^k\binom {k-n-1}k$) instead of explicitly remembering the formula for the coefficients of $(1-x)^n$ (the first identity, and more generally the use of binomial coefficients with "strange" upper indices, is a very useful tool, but there is no harm in remembering the latter as well, as it comes in handy rather often.).

-

I assume you look for integer non-negative solutions. Try to write your problem as follows: represent $x_i$ as a set of $1$ (i.e. if $x_1=3$, then write it as $111$.) Then put your signs of $+$. In the end, you have 12 symbols of $1$ ($x_i$ add to $12$) and 5 symbols of $+$ (you have 6 variables). Now, how many ways do you have to choose 5 symbols out of 12+5=17? Of course, $C_{17}^5=6188$.

For example, a solution $5+3+2+2+0+0=12$ looks like $11111+111+11+11++=12$.

-
Thank you, I did know another way of solving this is stick and stones, but I would also like to know if my way of solving is correct (even if the final answer is most probably correct). – ohad May 20 '13 at 10:54