Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search