# Integer solutions Help

How many integer solutions are there to $$x_1 +x_2 + \text{ ... }+x_5 =31 \;\; \text{ with } \; \; x_i \geq i, \;\; i=1,2,3,4,5$$

I tried it and got $C(20,16)$ but I don't really think that is correct...

-
Another way is to get rid of the conditions. If $x_i \ge i$, then replace $x_i$ with $i$ copies of $x_i$ with $x_i \ge 1$. Then we have that there are $1+2+3+4+5 = 15$ $x's$ which equal $1$ which makes this an easier problem. – Sandeep Silwal Apr 15 '14 at 18:15

By setting $y_i = x_i - i$ for $i = 1,...,5$ we see that the set of integer solutions to $x_1 + ... + x_5 = 31$ with $x_i \geq i$ is in bijection with the set of integer solutions to $y_1 + ... + y_5 = 31 - (1+2+3+4+5) = 16$ with $y_i \geq 0$.

The number of solutions to the latter can be found using the so called "balls in urns" formula. We can view the problem as distributing $16$ indistinguishable balls among $5$ urns. The solution is then $\binom{16+5-1}{5-1} = \binom{20}{4}$ and your answer was correct.

-

We are distributing $31$ identical candies among $5$ (non-identical) kids, with Kid $1$ getting at least $1$ candy, Kid $2$ getting at least $2$, and so on.

Initially, give $0$ candies to Kid $1$, $1$ to Kid $2$, and so on up to $4$ to Kid $5$. That takes care of $10$ candies, leaving $21$.

Then distribute the $21$ remaining candies among the kids, at least one to each. By Stars and Bars, there are $\binom{20}{4}$ ways to do this.

Alternately, initially give $1$ candy to Kid $1$, $2$ to Kid $2$, and so on. That leaves $16$ candies. Distribute these among the kids, with some perhaps getting $0$ additional candies. Again, standard Stars and Bars gives the answer $\binom{20}{4}$, or in some versions the equivalent $\binom{20}{16}$.

The expression you obtained is correct.

-

Let's look at this with a generating function. So $f_{i}(x)$, the function for constraint $i$ is $\sum_{j=i}^{\infty} x^{j} = x^{i} * \frac{1}{1-x}$, by a convergent geometric series.

So $f_{1}(x) = \sum_{j=1}^{\infty} x^{j} = \frac{x}{1-x}$. We now multiply the $f_{i}$ together to get $f(x) = \dfrac{x * x^{2} * x^{3} * x^{4} * x^{5}}{(1-x)^{5}}$.

We are looking for the coefficient of $x^{31}$. However, we divide out by $x^{15}$, the numerator of $f(x)$, which tells us now to look for the coefficient of $x^{16}$.

And so this is the stars and bars solution: $\binom{16 + 5 - 1}{16} = \binom{20}{16} = \binom{20}{4}$.

-