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

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