Numbers and Digit SumsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/