Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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?

share|improve this answer
    
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}$$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.