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.

Calculate number of solutions of the following equations:

$$ x_1 + x_2 + x_3 + x_4 = 15 $$

where $ 0 \le x_i < i + 4 $

I try to solve it using generating functions/enumerators :

$$ (1+x+x^2+x^3+x^4)(1+x+x^2+x^3+x^4+x^5)(1+x+x^2+x^3+x^4+x^5+x^6)(1+x+x^2+x^3+x^4+x^5+x^6+x^7)$$

and take coefficient near $15$. But I do not know how to quickly calculate it. Maybe there exists any faster way?

share|improve this question

3 Answers 3

up vote 5 down vote accepted

The expression you have is $$ \frac{1-x^5}{1-x}\frac{1-x^6}{1-x}\frac{1-x^7}{1-x}\frac{1-x^8}{1-x} $$ Then treat this as $$ (1-x^5)(1-x^6)(1-x^7)(1-x^8)(1-x)^{-4} $$ The $(1-x)^{-4}$ can be treated by taking derivatives for the geometric series $(1-x)^{-1}$, and you can easily compute the product of the first four terms. What you need is only the terms $c_k x^k$ where $k\leq 15$, and find $15-k$-th coefficient in $(1-x)^{-4}$.

share|improve this answer

To take a slightly different route from i707107's solution, once you obtain the product of rational functions, you can use the identity: and $$ \frac{1}{(1-x)^n} = 1 + \binom{1 + n -1}{1}x + \binom{2 + n -1}{2}x^2 + \dots + \binom{r + n -1}{r}x^r + \dots. $$ to expand the last term of the simplified product (2nd line) that i707107 has written. Then you would simply take product of the first $4$ polynomials, which isn't that bad since they're just $2$ terms each. Then you'd find the coefficient of the products that give $x^{15}$.

share|improve this answer

Use the stars and bars technique to solve for the number of solutions without restrictions, and look at how to count the solutions that violate the restrictions.

share|improve this answer
    
Yes, indeed, I think that now I know how to solve it. Thanks a lot. By the way, maybe someone has any idea how to find solution using approach with enumerators? –  JosephConrad Mar 24 '13 at 1:34
    
The factors you have are finite geometric series, perhaps expressing them that way simplifies the computations somewhat. –  vonbrand Mar 24 '13 at 1:37

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.