Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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 at 18:15

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.