I am asked to find the number of numbers between 1 and 10,000 whose sum of digits is 19. (I am aware that there's a similar question previously on here, but hear me out please, I have a different doubt).
When I assumed the number to be a 4 digit number with leading zeroes possible, I came up with the required situation as $$x_1+x_2+x_3+x_4 = 19$$
where $9\geq x_1,x_2,x_3,x_4\geq 0$
and the answer to the is the coefficient of $x^{19}$ in $(1+x+x^2+...+x^9)^4$ which is 660 which is the correct answer.
BUT I cant understand the mistake in the way I approached the question 1st, which was taking two cases.
1st Observation: Clearly, no 1 digit or 2 digit number satisfies, as the max value for 2 digit number is 9+9 = 18 (for 99) So, clearly, there remain two cases, a 3 digit and a 4 digit number.
Taking a 3 digit number, abc, $a \geq 1, b,c \geq 0$ (if a = 0 then wont be 3 digit)
Here, again, $a+b+c = 19$, and then, if i take $a-1 = k \geq 0$, then it turns out to be $$k+b+c=18$$ where $k,b,c \geq 0$. The required number of numbers of 3 digit would be:
The coefficient of $x^{18}$ in $(1+x+x^2+....+x^9)^3$
And, similarly taking the case for 4 digit numbers, the answer for that would be the coefficient of $x^{18}$ in $(1+x+x^2+....+x^9)^4$
And the total answer would be the sum of these two cases, but that came out to be greater than 660. What did I do wrong? Am I adding extra cases here? If so, how?
Since $a$ can only be from $1$ to $9$, and you subtract $1$ from $a$ so it starts at zero, $a-1$ ends at $8$, rather than $9$.
The contribution of $a-1$ would be $1+x+x^2+\ldots+x^8$, not $x^9$