# Counting problem homework

How many different six digit positive integers are there (duplicates allowed), where each digit is between 0 and 7 (inclusive), and the sum equals 20?

I know that there are 229,376 total possible 6 digit numbers which do not have an 8 or a 9. But what process do I use to eliminate those numbers whose digital sums do not equal 20?

-

The answer is the coefficient of $x^{20}$ in $$(x+x^2+\cdots+x^7)(1+x+\cdots+x^7)^5$$ Do you see why? Then the first bracket is $x(1-x^7)/(1-x)$, and then second is the 5th power of $(1-x^8)/(1-x)$. OK? So now you need to be able to expand $x(1-x^7)(1-x^8)^5(1-x)^{-6}$, and pick out the coefficient of $x^{20}$. Can you use the Binomial Theorem to do that?

-
 Still seems like a lot to do by hand. $(1-x^8)^5 = 1 - 5 x^8 + 10 x^{16} +$ (higher powers than $x^{20}$). Multiplying by $x - x^8$ is no problem. But then divide by $1-x$ six times, or multiply by $(1-x)^{-6} = 1 + 6 x + \ldots + 53130 x^{20} + \ldots$? – Robert Israel Nov 12 '12 at 7:00 @Robert, $(1-x)^{-6}=\sum{n+5\choose5}x^n$, so you'll wind up with a sum of 5 terms, each a small multiple of a binomial coefficient. If you want a number, you have to compute those binomials, but on homework many are happy with things like $14\choose5$ left unevaluated. – Gerry Myerson Nov 12 '12 at 12:10

You could use dynamical programming. Let $a(m,n)$ be the number of $m$-digit nonnegative integers with each digit 0 to 7 and the sum of digits is $n$. Then $a(1,n) = 1$ for $0 \le n \le 7$, $0$ otherwise, and $$a(m+1,n) = \sum_{d=0}^{\min(n,7)} a(m,n-d)$$

EDIT: That solution allows leading zeros. If leading zeros are not allowed, take $a(1,0) = 0$ as well.

EDIT: Let $a(m,n)$ be as above in the version with leading zeros not allowed, and $b(m,n)$ the version with leading zeros allowed. Then $a(6,20) = \sum_{k=0}^{20} a(3,k) b(3,20-k)$. For $m = 1,2,3$ we make the following tables:

 n   a(m,n)              b(m,n)
m=1     2     3     1     2    3
0      0     0     0     1     1     1
1      1     1     1     1     2     3
2      1     2     3     1     3     6
3      1     3     6     1     4    10
4      1     4    10     1     5    15
5      1     5    15     1     6    21
6      1     6    21     1     7    28
7      1     7    28     1     8    36
8      0     7    35     0     7    42
9      0     6    40     0     6    46
10      0     5    43     0     5    48
11      0     4    44     0     4    48
12      0     3    43     0     3    46
13      0     2    40     0     2    42
14      0     1    35     0     1    36
15      0     0    28     0     0    28
16      0     0    21     0     0    21
17      0     0    15     0     0    15
18      0     0    10     0     0    10
19      0     0     6     0     0     6
20      0     0     3     0     0     3


Then (going down the $a(3,n)$ column and up the $b(3,n)$ column) your answer is \eqalign{&0 \times 3 + 1 \times 6 + 3 \times 10 + 6 \times 15 + 10 \times 21 + 15 \times 28 + 21 \times 36 + \cr &28 \times 42 + 35 \times 46 + 40 \times 48 + 43 \times 48 + 44 \times 46 + 43 \times 42 + 40 \times 36 + \cr &35 \times 28 + 28 \times 21 + 21 \times 15 + 15 \times 10 + 10 \times 6 + 6 \times 3 + 3 \times 1 \cr}

-
 I have no idea how you would solve that. – Daniel Powell Nov 12 '12 at 1:06 Probably not by hand, but easy in any computer language or spreadsheet. – Robert Israel Nov 12 '12 at 1:09 This is a homework problem I must solve by hand. – Daniel Powell Nov 12 '12 at 1:14 Leading zeros are not allowed. 000001 is not a 6 digit number. It is the number 1. – Daniel Powell Nov 12 '12 at 1:20