Discrete Math/Combinatorics Question

[Rockoz]

Homework Statement

This question has two parts:

a) How many integers are there between 100 and 1,000,000 with the property that the sum of their digits is equal to 6?

b) How many integers are there between 100 and 1,000,000 with the property that the sum of their digits is less than 6?

Homework Equations

Theorem: The number of solutions in nonnegative integers of the equation
x1 + x2 + . . . + xn = k

is C(n+k-1,k) where C is for combination.

The Attempt at a Solution

part a) Here is how I tried to look at the problem. For integers between 100 and 1,000,000 we have integers of the form x1x2x3x4x5x6x7 where x1 + x2 + x3 + x4 + x5 + x6 + x7 = 6.
We must have x1 (the first digit) be equal to zero since we are between 100 an 1,000,000 and the case where x1= 1 wouldn't matter to us anyways. The other digits can be from 0 through 9. So we are left with x2+x3+x4+x5+x6+x7 = 6. The <=9 part doesn't matter here since the highest any of these xi's can be is 6. We solve for the number of solutions to this equation to get the number of integers. Using the theorem above I solve this as C(6+6-1,6) = C(11,6).

But I believe this is actually the answer for integers from 1-1,000,000 and so I have overcounted (I am including integers like 0000006). So I think what I can do here is subtract the integers from 1-100 whose digits add up to 6. For this we have integers of the form y1y2y3 where y1 = 0 and y2 and y3 can be 0 through 9. We have y2 + y3 = 6. Using the theorem above I have C(2 + 6 - 1,6) = C(7,6) integers.

So I think the answer for part a is C(11,6) - C(7,6) = 455

part b) I don't know how to approach this because of the less than part. Would I have to take this into cases (equal to 1,2,3,4,5) and then add these?

Thank you very much for your time.

 

[Infinitum]

The approach to part (a) seems correct

For the second one you need to use the same approach adding all the 5 cases.