how many different numbers are there with 3 digits and that add up to 19?

Question

Hi I can't figure out if there is a fast way to calculate how many different numbers are there with N(3) digits that add up to M(19) allowing leading 0 (if they add up to 15, 069 is a proper combination). It is obvious that with 3 we are constrained to 27(999). Is there a shorter path, which I can use? I saw some connection with the pascal triangle but it seems to be kinda rigid.

Answer 1

You’re looking for the number of solutions to the equation $x_1+x_2+x_3=19$ in integers $x_1,x_2,x_3$ satisfying the inequalities $0\le x_k\le 9$ for $k=1,2,3$. Without the upper limit of $9$ this is a standard stars-and-bars problem, whose answer

$$\binom{19+3-1}{3-1}=\binom{21}2\;;\tag{1}$$

the general formula and a pretty clear derivation are given at the link. However, this counts solutions like $1+10+8$ in which some variable exceeds the limit of $9$. Let $y_1=x_1-10$, $y_2=x_2$, and $y_3=x_3$; then a solution $x_1+x_2+x_3=19$ in which $x_1>9$ corresponds to a solution to $y_1+y_2+y_3=9$. There are

$$\binom{9+3-1}{3-1}=\binom{11}2$$

such solutions. Similarly, there are $\binom{11}2$ solutions to $x_1+x_2+x_3=19$ in which $x_2>9$ and $\binom{11}2$ in which $x_3>9$. Removing these from the preliminary count $(1)$ leaves a total of

$$\binom{21}2-3\binom{11}2=210-3\cdot55=45$$

three-digit integers of the desired type. No further corrections are needed, since the equation $x_1+x_2+x_3=19$ has no solutions in non-negative integers in which more than one variable exceeds $9$.

Answer 2

Dynamic programming (or call it recursion if you like, since no optimization is involved).

Let $f[i,j]$ be the number of $i$-digit numbers whose digits sum to $j$.

Then $f[i,j]=\sum_{p=0}^{\min(9,j)}f[i-1,j-p]$ ($p$ is the digit at position $i$), with some simple boundary conditions. This results in an algorithm of $\mathcal{O}(NM)$.

Applying to your problem, that is to make a table of 3*19 (with many zeros) and fill it with the formula.

The algorithm is good for larger cases. 3 digits are just too few to see the power of the algorithm.