1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Don't worry about $0$. No sum of three digits that includes $0$ adds up to $19$. $\endgroup$ – Carlos Eugenio Thompson Pinzón Oct 25 '13 at 22:10
  • $\begingroup$ Yes but if you have 15 069 will be proper $\endgroup$ – AlexRu Oct 25 '13 at 22:12
  • 4
    $\begingroup$ This sounds like the number of non-negative integral solutions to the equation $a+b+c=19$ where $a$, $b$, and $c$ $\in\{1,2,...,9\}$. $\endgroup$ – 1233dfv Oct 25 '13 at 22:28
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Well done! This is so thorough and helpful! Thank you :) $\endgroup$ – 1233dfv Oct 26 '13 at 6:47
  • $\begingroup$ @Ross: You’re welcome! $\endgroup$ – Brian M. Scott Oct 26 '13 at 6:58
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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