All topics

s5.2.6

Counting Problems with Digits

1,000 questions

"How many 3-digit numbers have digits summing to nn?" is a stars-and-bars count with a constraint: the leading digit cannot be zero and no digit exceeds 9.

Substitute a=a+1a = a' + 1 so the leading digit starts at zero, then count solutions of a+b+c=n1a' + b + c = n - 1 with each at most 9. Without the upper bound that is (n+12)\binom{n+1}{2}; subtract the cases where one variable exceeds 9.

For small nn the bound never bites, so the answer is just (n+12)\binom{n+1}{2}.

Practise this