Generating function to find the sum of digits

Question

How many integers between $30,000$ and $100,000$ have a sum of $15$ or less?

I was approaching this problem with a generating function:

$$g(x) = (x^3+x^4+x^5+x^6+x^7+x^8+x^9)(1+x+...+x^9)^4$$

First I'm going to pull out $x^3$ then I would need the coefficients of $x$ to the $15$th, $14$th, $13$th etc correct? If so, can someone help me through finding the coefficients?

Also finding the coefficient of x to the 15th would be the same as finding the coefficient of x to the 12 is I pull out x$^3$

Answer 1

Assuming you are including $30\,000$ and excluding $100\,000$.

Write:

$$\sum_{k=3}^{9}x^k=\frac{x^3-x^{10}}{1-x}\, ,$$ $$\sum_{k=0}^{9}x^k=\frac{1-x^{10}}{1-x}\, .$$

Then

$$g(x)=\left(\sum_{k=3}^{9}x^k\right)\left(\sum_{k=0}^{9}x^k\right)^4=\frac{x^3-x^{10}}{1-x}\left(\frac{1-x^{10}}{1-x}\right)^4$$

Use the operator $(1-x)^{-1}=1+x+x^2+x^3+\cdots$. Then the coefficient of $x^{15}$ in

$$\frac{1}{1-x}g(x)$$

is the required answer.

Now

$$(x^3-x^{10})(1-x^{10})^4=\sum_{r=0}^{4}(-1)^{r}\binom{4}{r}x^{10r+3}-\sum_{r=0}^{4}(-1)^{r}\binom{4}{r}x^{10r+10}\, ,$$

and therefore, since $(1-x)^{-6}=\sum_{k\ge 0}\binom{5+k}{5}x^k$, we have

$$\begin{align}(1-x)^{-1}g(x)=&\left(\sum_{r=0}^{4}(-1)^r\binom{4}{r}x^{10r+3}\right)\left(\sum_{k\ge 0}\binom{5+k}{5}x^k\right)\\[1ex] &- \left(\sum_{r=0}^{4}(-1)^r\binom{4}{r}x^{10r+10}\right)\left(\sum_{k\ge 0}\binom{5+k}{5}x^k\right)\, ,\\[1ex] =& \sum_{k\ge 0}\left(\sum_{r\ge 0}(-1)^r\binom{4}{r}\binom{k+2-10r}{5}\right)x^{k}\\[1ex] &-\sum_{k\ge 0}\left(\sum_{r\ge 0}(-1)^r\binom{4}{r}\binom{k-10r-5}{5}\right)x^{k}\, .\end{align}$$

Taking the $x^{15}$ coefficient gives

$$\begin{align}[x^{15}](1-x)^{-1}g(x)&=\sum_{r\ge 0}(-1)^r\binom{4}{r}\binom{17-10r}{5}-\sum_{r\ge 0}(-1)^r\binom{4}{r}\binom{10-10r}{5}\, ,\\[1ex] &=\binom{4}{0}\binom{17}{5}-\binom{4}{1}\binom{7}{5}-\binom{4}{0}\binom{10}{5}\, ,\\[1ex] &=\binom{17}{5}-4\binom{7}{5}-\binom{10}{5}\, ,\\[1ex] &=5852\, .\tag{Answer}\end{align}$$

Answer 2

My first thought about this problem was, "blargh, too horrible to do by hand." But actually, it's not so bad if we take a shortcut.

Let's just focus on the $(1+x+\cdots+x^9)^4$ part. A simpler quantity to expand is $(1+x+x^2+\cdots)^4 = (1-x)^{-4}$. Just as coefficients of $(1+x)^n$ give rows of Pascal's triangle, coefficients of $(1-x)^{-4}$ give diagonals. So \begin{equation} (1+x+x^2+\cdots)^4 = 1+4x+10x^2+20x^3+35x^4+56x^5+84x^6+120x^7+165x^8+220x^9+286x^{10}+364x^{11}+455x^{12}+\cdots. \end{equation} What about $(1+x+\cdots+x^9)^4$? It agrees with the above up through the $x^9$ term, so you only need to modify the last three. The problem with these three is that they include counts of "forbidden" four-digit strings, which we might think of as "hexadecimal". Thus the $286 x^{10}$ term includes counts of A000, 0A00, 00A0, and 000A. Excluding these four cases yields $282 x^{10}$. Similarly, $364 x^{11}$ includes B000, A100, and their permutations ($4+12 = 16$ cases), and $455 x^{12}$ includes all permutations of C000, B100, A200, and A110 ($4+12+12+12=40$ cases). Therefore \begin{equation} (1+x+\cdots+x^9)^4 = 1+4x+10x^2+20x^3+35x^4+56x^5+84x^6+120x^7+165x^8+220x^9+282x^{10}+348x^{11}+415x^{12}+\cdots. \end{equation} The final step is to multiply this by $1+x+\cdots+x^6$. We can take the next diagonal of Pascal's triangle to get the coefficients up through $x^6$. Or, equivalently, we can just make a running sum of the coefficients above: $1$, $1+4 = 5$, $5+10 = 15$, etc., up to $126+84 = 210$ at $x^6$. After this point you could multiply by $1+x+\cdots+x^6$ directly. This amounts to taking sums of $7$ consecutive coefficients in the expansion above. E.g., the coefficient of $x^{10}$ would be the sum $35+56+84+120+165+220+282 = 962$. You can simplify this calculation by adding new coefficients on one end and subtracting them from the other: the coefficient of $x^{11}$ would be $962+348-35 = 1275$.

Once you have this expansion, you simply add up the coefficients for $x^0$ through $x^{12}$ and you're done, as you suggest...

But wait! Actually you're off by one. What we've done here applies to the numbers $30,000$ through $99,999$. You'd have to subtract one to omit the $30,000$ case, or else add one to include $100,000$ if you meant "inclusive".

Answer 3

We want the number of solutions in integers to $$x_1+x_2+x_3+x_4+x_5 \le 15$$ where $3 \le x_1 \le 9$ and $0 \le x_i \le 9$ for $2 \le i \le 5$. This is the same as the number of solutions to $$x_1+x_2+x_3+x_4+x_5+x_6 = 15$$ with the additional constraint $0 \le x_6$. More generally, we seek the generating function of the number of solutions $a_r$ to $$x_1+x_2+x_3+x_4+x_5+x_6 = r$$ with the above constraints.

The generating function is $$\begin{align} f(x) &= (x^3 + x^4 + x^5 + \dots +x^9) (1+x+x^2+\dots +x^9)^4(1+x+x^2+\dots) \\ &=x^3 \cdot \frac{1-x^7}{1-x} \cdot \left( \frac{1-x^{10}}{1-x} \right)^4 \cdot \frac{1}{1-x} \\ &=x^3 (1-x^7)(1-x^{10})^4 (1-x)^{-6} \\ &= x^3 (1-x^7) \cdot \sum_{i=0}^4 (-1)^i \binom{4}{i} x^{10i} \cdot \sum_{j=0}^{\infty} \binom{6+j-1}{j} x^j \end{align}$$ From the final equation above we can extract the coefficient of $x^{15}$: $$a_{15}=\binom{6+12-1}{12}-\binom{4}{1} \binom{6+2-1}{2}-\binom{6+5-1}{5} = \boxed{5852}$$