How many natural numbers less than one million have the sum of their digits equal to 12?
You actually don't need a computer if you have a good method!
Each valid natural number can be mapped to a ordered non-empty partition of 18 by adding 1 to each digit. Example 930000 -> 10,4,1,1,1,1.
There are 17C5=6188 partitions of 18. However some of these partitions have elements of size 11, 12, or 13.
There are 6*(6C4)=90 partitions which have an 11, 6*(5C4)=30 partitions which have a 12, and 6*(4C4)=6 partitions which have a 13.
Subtract these out from the earlier total to get 6188-90-30-6 = 6062 as the final answer.
Analytic Solution
