Saturday, March 8, 2008

How many positive integers less than 1,000, 000 have exactly one digit equal to 9 and have a sum of digits equal to 13?

Solution.

There are six choices for the position where 9 appears.


After that choice has been made, the problem reduces to figuring out how many ways are there to select a sequence of five positive integers summing to 4 (since 13 − 9=4).

This is the same as counting permutations of four stars and four bars; the first integer in the sequence corresponds to the number of stars before the first bar, the second to the number of stars between first and second bars, etc.

The total number of ways to permute four stars and four bars is Bin(8,4) . Therefore th number of positive integers less than 1, 000, 000 that have exactly one digit equal to 9 and the sum of digits equal to 13 is 6 Bin(8,4) .

No comments: