How many numbers are less than million such that their digits sum is $\le 19$?

Question

How many numbers are less than million such that their digits sum is $\le 19$?

This question is a Generating-Functions exercise.

The solution claims the answer is the coefficient of $x^{19}$ in:

$$ \left( 1 + x + x^2 + ... + x^9 \right)^6 \left(\frac{1}{1-x}\right) $$

The left term is obvious, but why multiplying by $\frac{1}{1-x}$?

In general, if $F(x)$ generates $a_n$ then $\frac{F(x)}{1-x}$ generates $\sum\limits_{k=0}^n a_k$, but I don't see is that fitting here.

Answer 1

This has already been hinted in a comment, but if $$F(x) = (1 + x^2 + x^3 + x^4 + x^5 +x ^6 + x^7 + x^8 + x^9)^6,$$ then the coefficient of $x^{19}$ in $F(x)$ is the number of non-negative integers less than $10^6$ for which the sum of digits of the integer's decimal representation is exactly $19.$

But you want the sum of digits to be at most $19,$ so you want the sum of coefficients of the first twenty terms of $F(x)$ (that is, terms where the exponent of $x$ ranges from $0$ to $19$), which as you already know is the coefficient of $x^{19}$ in the series representation of $\dfrac{F(x)}{1 - x}.$

Answer 2

I wrote some code in java to brute force this problem, and I got the answer 147,070. I'll put the code below.

(NOTE: Now I noticed that this doesn't exactly answer your question, but I'll just leave it in case it's helpful to somebody at some point in time.)

public class million {
   public static void main(String args[]) {
       int x = 0;
       int counter = 0;

       while (x < 1000000) {
           int test = x;
           int sum = 0;

           while (test > 0) {
                sum += test % 10;
                test = test / 10;
            }

           if (sum <= 19) {
               counter += 1;
           }    

       x += 1;
       }

       System.out.println(counter);
   }
}