1
$\begingroup$

I have been looking at some simpler versions where digits sum < 9 example: from 1 to $10^4$ how many sum to 5? using repeated combinations $\binom{5+5−1}{5}=\binom{9}{5}=126$ however the given answer is 56

does a generalized version (formula) exist where R = sum of digits ; N = number of digits. $ A \leq N \leq B $

in the example above$ R = 5; N = 5; A = 1; B = 5; $

1 Answers 1

2

Your error is that the numbers between $1$ and $10^4$ don't have 5 digits; they have at most $4$ digits, except for the largest one, $10^4 = 10000$, whose digits don't add up to $5$.

Instead, you need to count the number of $4$-tuples that add up to $5$; these will correspond to numbers between $0$ ($=0000$) and $9999$ whose digits add up to $5$. So the correct formula would be $\binom{4+5-1}{5} = \binom{8}{5} = 56.$ Your binomial coefficient counts, instead, the number between $1$ and $10^5$ whose digits add up to $5$ (by counting those between $0$ and $99,999$).

  • 0
    The analysis in Brian Scott's answer is easily generalizable; I think you *will* have to do it by subtraction, though, rather than some simple "direct" formula.2012-02-23