# generating functions / combinatorics

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?

-

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

-

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.

-
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

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

-