Numbers and Digit Sums

Date: 12/03/97 at 13:08:41
From: Omer Moltay
Subject: Problem involving numbers and digit sums.

How many numbers between 0 and 99,999 are there whose digits add up 
to 20?

I have solved this problem by writing a computer program; however, I 
am looking for a mathematical formula that will give the result. The 
answer I got from the computer is 6300.

Thank you!

Date: 12/03/97 at 16:11:36
From: Doctor Rob
Subject: Re: Problem involving numbers and digit sums.

I can't give you a formula, but I can tell you a fast way to describe
the answer. It is the coefficient of x^20 in the expansion of

   G(x) = (1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9)^5,
        = (1 - x^10)^5/(1 - x)^5,

which my computer says is 5631.

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 12/04/97 at 10:15:56
From: =?iso-8859-3?Q?=D6?=mer Moltay
Subject: Re: Problem involving numbers and digit sums.

How did you come up with that polynomial expression? Is it derived 
from combinatorics? And how did your computer calculate the 
coefficient of x^20?

Thanks.

Date: 12/04/97 at 11:31:45
From: Doctor Rob
Subject: Re: Problem involving numbers and digit sums.

This is from a part of mathematics called "Generating Functions."  
The variable x is just an accounting device. Its exponent tells you 
the value of the digit in a particular column. Its coefficient tells 
you how many times that digit occurs there. For each column, the 
digits from 0 to 9 are possible, and each can occur only one time, so 
the generating function of each column is 1*x^0 + 1*x^1 + ... + 1*x^9.  
Since the five columns are independent of each other, the generating 
function for them jointly is the 5th power of this. The sum of the 
digits will be the exponent of x in this product, and the coefficient 
of x^k will be the number of ways that the sum can add up to k.

Think of it this way.  Each number represents picking one term from 
each of the five factors, and multiplying them together. If the digits 
add up to k, the power of x in this product will be x^k (think about 
it!) and the product of the coefficients, 1, will contribute +1 to the 
coefficient of x^k in the product.

Let's see how that works for sum of digits equal to 0.  The only 
number is 00000 = 0, and that corresponds to picking the term x^0 = 1 
from all five factors, whose product is 1^5 = 1. The coefficient of 
x^0 in the product is then computed as the sum of this single term, 
and you get the answer 1.

Now let's try the sum of digits equal to 1. The term in the product
containing x^1 can be gotten by choosing x from one of the five 
factors and 1 from the other 4, giving a product of x*1^4 = x. 
Since there are five ways to pick one of the five factors, there 
should be in the product five x terms, and the product must look 
like 1 + 5*x + ...  Sure enough, the five numbers are 
00001 = 1, 00010 = 10, 00100 = 100, 01000 = 1000, and 10000.

Now let's try the sum of digits equal to 2.  The term in the product
containing x^2 can be gotten in two different ways:  by choosing x 
from two of the five factors, and 1 from the other 3 (5 choose 2 or 10 
ways to do this), or by choosing x^2 from one of the five factors and 
1 from the other 4 (5 choose 1 or 5 ways to do this). In total there 
are 15 ways to do this, corresponding to the 10 rearrangements of 
00011 and the five rearrangements of 00002.  The numbers are 2, 11, 
20, 101, 110, 200, 1001, 1010, 1100, 2000, 10001, 10010, 10100, 11000, 
and 20000.

How did my computer do this?  I used Mathematica(TM), a symbolic 
algebra package produced by Wolfram Research, Inc. It just expanded 
this algebraic expression out using the rules of algebra.

For this particular computation, there is a way to do it using paper 
and pencil that is pretty easy, involving only a moderate amount of
arithmetic. Write down 10 1's in a row, followed by 36 0's, 
representing the coefficients of the powers of x from 0 to 45 in 
(1 + x + ... + x^9)^1.

1  1  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0  ...

Starting from the left, below this row make a new row.  Each entry in 
the new row will be the sum of the number above it and its 9 neighboring
numbers to its left (if there are fewer than 9, just use what you 
have). The resulting new row should look like this:

1  2  3  4  5  6  7  8  9  10  9  8  7  6  5  4  3  2  1  0  0 ...

The second row represents the coefficients of powers of x from 0 to 45 
in (1 + x + ... + x^9)^2.  Now make a third row from the second using 
the same rule:

1  3  6  10  15  21  28  36  45  55  63  69  73  75  75  73  69  63   
55  45  36 ...

These are the coefficients of (1 + x + ... + x^9)^3.  A good check 
is that the nonzero numbers read the same forward and backward. 
Another check is that if you add them all up, you should get 
10^3 = 1000 (set x = 1). Now make a fourth row

1    4   10   20   35   56   84  120  165  220  282  348  415  480  
540  592  633  660  670  660  633 ...

and a fifth row

1    5   15   35   70  126  210  330  495  715  996 1340 1745 2205 
2710 3246 3795 4335 4840 5280 5631 5875 6000 6000 5875 5631 ...

all using the same rule, using the same kind of checks. The 21st 
number in the 5th row, 5631, is the one you want, the coefficient of 
x^20 in (1 + x + ... + x^9)^5.

By the way, the coefficients in the 5th row tell you how many integers
between 0 and 99999 have digit sums equal to each of the numbers from 
0 through 45, so you have solved all those problems at once!

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/