Generating functions. Number of solutions of equation.

Question

Let's consider two equations

$x_1+x_2+\cdots+x_{19}=9$, where $x_i \le 1$

and

$x_1+x_2+\cdots+x_{10}=10, $ where $ x_i \le 5$

The point is to find whose equation has greater number of solutions

What I have found is:

number of solutions for first equation: $\binom{19}{9}=92378$

generating function for the second equation: $$\left(\frac{1-x^6}{1-x}\right)^{10}=(1-x^6)^{10} \cdot (1-x)^{-10}$$

Here I completely do not know how to find number near $[x^{10}]$ coefficient. Wolfram said that it is $85228$, so theoretically I have solution, but I would like to know more generic way how to solve such problems. Any ideas?

Answer 1

You have by standard formulas $(1-x^6)^{10}=\sum_{i=0}^{10}(-1)^i\binom{10}ix^{6i}$ and $(1-x)^{-10}=\sum_{i=0}^\infty\binom{9+i}9x^i$. Since you are only interested the the coefficient of $x^{10}$ in the product, you may ignore the terms with higher powers in these series. This reduces the first one to $1-10x^6$; the second one requires computing more binomial coefficients. But you don't need all terms of the series, because only the terms of degree $10$ and $10-6=4$ will contribute to the coefficent of $x^{10}$ in the product. These terms are respectively $\binom{19}9x^{10}$ and $\binom{13}9x^4$, and the coefficient of $x^{10}$ you are after is $$ \binom{19}9-10\binom{13}9. $$ Hey, the first term is precisely what you had for the first problem, so without even computing these binomial coefficients you can see that the second problem has less solutions. The difference is $10\binom{13}9=7150$.

Now was that an accident? Not really. If you would count the number of solutions of the second problem without the restriction that each $x_i\leq 5$, the a standard argument would reduce it to something equivalent the first problem. Indeed if you replace, in order, each term $x_i\geq0$ in a second solution by a sequence of $x_i$ terms $0$, and each of the nine $+$ signs into a term $1$ separating those zeros, then you have a solution for the first problem, and the correspondence is bijective (any solution for the first problem comes from a unique one of the modified second problem). So it is precisely the restrictions $x_i\leq 5$ that are responsible for the difference between the outcomes.

Answer 2

Generating functions is a generic way.

To continue on your attempt, you can apply Binomial theorem, which applies to negative exponents too!

We have that

$$ (1-x)^{-r} = \sum_{n=0}^{\infty} \binom{-r}{n} (-x)^n$$ where

$$\binom{-r}{n} = \dfrac{-r \times (-r -1) \times \dots \times (-r - n +1)}{n!} = (-1)^n\dfrac{r(r+1)\dots(n+r-1)}{n!} $$

Thus

$$ \binom{-r}{n} =(-1)^n\binom{n + r- 1}{n}$$

And so

$$ (1-x)^{-r} = \sum_{n=0}^{\infty} \binom{n +r -1}{n} x^n$$

Now your problem becomes finding the coefficient in the product of two polynomials, as you can truncate the infinite one for exponents $\gt 10$.

I will leave that to you.