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
    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$?2012-11-12
  • 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
    I have no idea how you would solve that.2012-11-12
  • 0
    Probably not by hand, but easy in any computer language or spreadsheet.2012-11-12
  • 0
    This is a homework problem I must solve by hand.2012-11-12
  • 0
    Leading zeros are not allowed. 000001 is not a 6 digit number. It is the number 1.2012-11-12