How many integers between [3,000, 8,000] have digit sum 20?

Question

Well, I've been almost losing my mind over this one.

The question is: How many integers on the interval $[3000, 8000]$ have a digit sum of 20?

Well, the first thing I did was separating to groups according to the first digit. and then:

3- A+B+C=17

4- A+B+C=16

5- A+B+C=15

6- A+B+C=14

7- A+B+C=13

Now my main problem is: Since A, B, and C are digits, it means that they are on the interval $[0, 9]$. How do I take that restriction into account?

Answer 1

Method 1: Using generating functions, you want the coefficient of $x^{20}$ in $$(x^3+x^4+ \ldots +x^7)(1+x+ \ldots +x^9)^3=\frac{x^3(1-x^5)(1-x^{10})^3}{(1-x)^4}$$

Equivalently, we drop the $x^3$ factor and look for the coefficient of $x^{17}$.

We have $(1-x)^{-4}=\sum_{i=0}^{\infty}{\binom{i+3}{3}x^i}$. Expanding $(1-x^5)(1-x^{10})^3$ and ignoring $x^n, n>17$ gives $(1-x^5)(1-3x^{10})=1-x^5-3x^{10}+3x^{15}$.

Finally the coefficient of $x^{17}$ is $$\binom{(17-0)+3}{3}-\binom{(17-5)+3}{3}-3\binom{(17-10)+3}{3}+3\binom{(17-15)+3}{3}$$

which easily evaluates to give $355$.

Method 2: As you might not be familiar with generating functions, here is a more elementary approach.

We proceed exactly as you did. If the 1st digit is $i$, then we have $A+B+C=20-i$. This gives $\binom{(20-i)+2}{2}$, but we have also counted those where $A, B, C$ are $\geq 10$. For those cases, exactly 1 of the digits is $\geq 10$. If it is $A$, we have $A=k=10, 11, \ldots , 20-i$. Then $B+C=20-i-k$, giving $21-i-k$ ways. The number of ways for $B, C$ are the same. Therefore we must subtract $3\sum\limits_{k=10}^{20-i}{(21-i-k)}=3\sum\limits_{j=1}^{11-i}{j}=3\frac{(11-i)(12-i)}{2}$.

Therefore the total number is

$$\sum_{i=3}^{7}{\left(\binom{(20-i)+2}{2}-3\frac{(11-i)(12-i)}{2}\right)}=355$$