Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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; $$

share|improve this question

1 Answer 1

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$).

share|improve this answer
    
aha thx! i am still wondering if there is a generalized version (maybe using hockey stick identity etc..because as soon as the sum of digits cross 10 i have to keep subtracting wrong ones...kinda like this one.. math.stackexchange.com/questions/65934/… –  user25596 Feb 23 '12 at 20:22
    
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. –  Arturo Magidin Feb 23 '12 at 21:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.