3
$\begingroup$

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?

2 Answers 2

4

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?

  • 0
    @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.2012-11-12
1

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}$

  • 0
    Leading zeros are not allowed. 000001 is not a 6 digit number. It is the number 1.2012-11-12