I also got 35. Did it the old fashioned way so there may be an error. Note we can't pick any digit to be 5 either because there would be 4 more digits to pick each of which must be at least 1 so the total sum becomes > 8.
1) Pick the first digit to be 4 then all other digits must be 1
4 1 1 1 1
there are 5 positions where 4 can go so there are 5 of these numbers.
2) Pick the first digit to be 3 then we cannot pick another 3 because we would go over. Pick the second digit 2
3 2
now , all remaining digits must be 1
3 2 1 1 1
keeping 3 fixed , there are four positions for 2. Since there are five positions for 3 we use the multiplication principle to get 5×4 = 20 of these numbers.
3) Pick the first digit to be 2. There is no need to pick 3 as any digit because that has been done already above at 2). Pick the second digit to be 2
2 2
the sum is already 4. now there are three digits remaining to pick and one of them must be 2
2 2 2
we are forced to pick 1 for the remaining digits
2 2 2 1 1
let's work with the 1's switching their position. We can use the same argument as before to get 5×4 = 20 but now we divide by two because the digits switching position are equal. There are 10 of these numbers.
There is no need to pick the first digit to be 1 because all possible configurations have been counted already. We are done counting.
5 + 20 + 10 = 35
Suppose you can have "digits" of any size. If you imgagine filling up the digits by adding 1 to each of them one at a time, you have to put a 1 in the first one to begin with. After that, you have 14 1's to place into the 10 digits. Now you can imagine arranging 14 1's and 9 + signs to achieve the same effect. That is, we have 23 symbols and we have to choose 9 of them to be + signs. So the number of ways to do this is:
$$
\begin{align}
&\text{Ways to choose digits adding to 15}\\
&\text{ with more than 9 allowed in some digits} ={{23}\choose{9}}
\end{align}
$$
However, we have included some options where there are more than nine in a position. If there are 10 dots anywhere, then there can't be another one with 10 because they won't add to 15. So we can safely count the ways for the rest to add to 5. Note that if one of them has 10 1's to begin with and we then add extra 1's this will cover ways when there are allowed to be more than 10 in that spot.
If the first "digit" is 10 or more, we put 10 1's in that position, and then we have 5 1's left to place between 9 + signs. So that's 14 symbols where we need to choose 9 to be + signs. So we get this many ways with 10 or more in the first digit:
$$
\begin{align}
&\text{Ways to fill digits adding to 15}\\
&\text{ with 10 or more in only the first digit} ={{14}\choose{9}}
\end{align}
$$
If some other digit is 10 or more, then we'll put 10 1's in that position. We have to put a 1 in the first position too. So now there are 4 1's left to place between 9 + signs. This is 13 symbols, 9 of which must be + signs. So for each other digit position we get:
$$
\begin{align}
&\text{Ways to fill digits adding to 15}\\
&\text{with 10 or more in a particular digit other than first} = {{13}\choose{9}}
\end{align}
$$
There are 9 digits to choose from, so we have:
$$
\begin{align}
&\text{Ways to fill digits adding to 15}\\
&\text{with 10 or more in any one digit} = {{14}\choose{9}} + 9{{13}\choose{9}}
\end{align}
$$
Hence, subtracting this from the total ways to fill digits we get the final answer:
$$
\begin{align}
&\text{Ways to fill digits adding to 15} \\
&\text{so there are no more than 9 in any digit} = {{23}\choose{9}} - {{14}\choose{9}} - 9{{13}\choose{9}}
\end{align}
$$
You could also use generating functions:
1st digit could be 1-9 so that corresponds to $(x+\dots+x^9)$. The other digits could be 0-9 which corresponds to $(1+x+\dots+x^9)$. So the number of ways to do it is the coefficient of $x^{15}$ in this expression:
$$
\begin{align}
(x+\dots+x^9)(1+x+\dots+x^9)^9 &= x(1+\dots+x^8)\left( \frac{1-x^{10}}{1-x} \right)^9\\
&= x\frac{1-x^9}{1-x}\frac{(1-x^{10})^9}{(1-x)^9}\\
&= x \frac{(1-x^9)(1-x^{10})^9 }{(1-x)^{10}}\\
&= x (1-x^9)(1-x^{10})^9(1-x)^{-10}\\
&= x(1-x^9)\left(1-{9\choose1}x^{10}+{9\choose2}x^{20} - \dots\right)\\
&\quad \times \left(1 -{{-10}\choose{1}}x + {{-10}\choose2}x^{2} - {{-10}\choose3}x^{3} + \dots \right)
\end{align}
$$
In order to produce an $x^{15}$, we choose terms from the four multiplicands. We have these options:
- $x \times 1 \times 1 \times {{-10}\choose{14}}x^{14}$
- $x \times 1 \times -{9\choose 1}x^{10} \times {{-10}\choose{4}}x^4$
- $x \times - x^9 \times 1 \times - {{-10}\choose{5}}x^5$
So the total number of options is:
$$
\begin{align}
{{-10}\choose{14}} - {9 \choose 1}{{-10}\choose{4}} + {{-10}\choose{5}}
&={{23}\choose{14}} - {9\choose 1}{{13}\choose{4}} - {{14}\choose{5}}\\
&={{23}\choose{9}} - 9{{13}\choose{9}} - {{14}\choose{9}}
\end{align}
$$
Best Answer
You're half-correct. By stars and bars, the number of solutions to $$x_1+x_2+x_3+x_4=8$$ is exactly $\binom{8+4-1}{4-1}=165$. I don't understand however why numbers like $8=0008$ don't count, since, as Thomas Andrews pointed out in the comments, the sum of its digits add up to $8$.
However, for $16$, our approach cannot be exactly the same, since a solution to $x_1+x_2+x_3+x_4=16$ could be $(x_1,x_2,x_3,x_4)=(1,2,3,10)$, but $10$ cannot be a digit, as those are always between $0$ and $9$. Since only one can be $10$ or larger, we can simply count the number of solutions where one is $10,11,\cdots,16$. If one is $10$, then we count the number of solutions to $x_1+x_2+x_3=16-10=6$. Use stars and bars again and we get $\binom{6+3-1}{3-1}$. Now we multiply by $4$ since we now chose $x_4=10$ but we also need to count $x_1,x_2,x_3=10$. So we get $4\binom{6+3-1}{3-1}$. Using this principle we get $$4\left(\binom{6+3-1}{3-1}+\binom{5+3-1}{3-1}+\cdots+\binom{0+3-1}{3-1}\right)=4\cdot84=336$$ The total amount of solutions to $x_1+x_2+x_3+x_4=16$, including those we don't want, are (again, stars and bars) $\binom{16+4-1}{4-1}=969$. Now substract the amount of solutions we don't want, and we get $969-336=633$ possibilities.