# If the sum of digits of a number is 17 and none of its digits is zero, we called it a ‘good number’. Find the number of 5-digit ‘good number(s)’.

Here's what I have done: since 5 digits are at least 1, that leaves the value 17-5 = 12 to be distributed in the rest of the digits so right now, the number is 11,111. the value 12 is distributed into the 5 digits, and using the stars and bars method, the answer should be 16C4 = 1820

What am I doing wrong (btw, the answer shows as 1645, but I don't know how)

• You can't use Stars and Bars directly, since the digits are capped. You'll have to exclude those combinations which would require a digit $>9$.
– lulu
Dec 30, 2023 at 14:49
• To verify that 1645 is correct, with brute force, you can use PARI/GP in which false is represented as 0, and true as 1, and therefore the expression sum(n=10000,99999,d=digits(n);vecmin(d)>0&&vecsum(d)==17) gives you the result (indeed 1645). Of course, this is not an answer. Dec 31, 2023 at 12:08
• Extended problem: Find the number of good numbers regardless of digit count (number of digits could be anything between 2 and 17). Dec 31, 2023 at 12:14

You have to exclude the numbers with “digits” equal to 10, 11, 12, 13 from consideration. Those numbers are (with random digits order):

$$13, 1, 1, 1, 1$$

$$12, 2, 1, 1, 1$$

$$11, 3, 1, 1, 1$$

$$11, 2, 2, 1, 1$$

$$10, 4, 1, 1, 1$$

$$10, 3, 2, 1, 1$$

$$10, 2, 2, 2, 1$$

The quantities of those numbers are the following:

$$5$$

$$5 \cdot 4 = 20$$

$$5 \cdot 4 = 20$$

$$5 \cdot 6 = 30$$

$$5 \cdot 4 = 20$$

$$5 \cdot 4 \cdot 3 = 60$$

$$5 \cdot 4 = 20$$

Substracting these numbers from your answer $$1820$$ gives the right answer $$1645$$

We can solve this question using fairly simple combinatorics.

Let each digit be represented as $$A, B, C, D$$ and $$E$$. In this manner, 1 $$\leq A \leq 9$$, 1 $$\leq B \leq 9$$, and so on.

This is the equivalent of finding the coefficient of $$x^{17}$$ in

$$(x^{1}+x^{2}+x^{3}+x^{4}+x^{5}+x^{6}+x^{7}+x^{8}+x^{9})^{5}$$ We can further simplify this as:

$$x^{5}(1-x^{9})^{5}(1-x)^{-5}$$

So, coefficient of $$x^{17}$$ becomes $$^{5+12-1}C_{12}\times ^{5}C_{0} - ^{5}C_{1} \times ^{5+3-1}C_{3}$$

$$=^{16}C_{12}-5\times ^{7}C_{3}$$

$$=1645$$

Hope this helped.

This is a kind of fun answer. Let M be the matrix $$\left( \begin{array}{ccccccccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \right).$$ The answer for finding the number of $$k$$ digit numbers whose digits do not include 0 and sum to $$k+j$$ is equal to the first element in the $$j$$th row of $$M^k$$ if $$j<=12$$.

Polynomial Method Another very similar method is to use powers of $$f(z) = z + z^2 +\cdots + z^9$$.
The number of $$k$$ digit numbers whose digits do not include 0 and sum to $$j$$ is equal to the coefficient of $$z^j$$ of $$(f(z))^k$$. Note that $$f(z) =\frac{z^{10}-1}{z-1}-1$$ and that for any polynomial $$p(z)$$, the coefficient of $$z^j$$ is $$c = p^{(j)}(0)/j!$$ where $$p^{(j)}$$ is the $$j$$th derivative of $$p$$.

As indicated by the comment of lulu, if Stars and Bars is to be used, it must be combined with Inclusion-Exclusion. I will follow the approach taken in this answer.

You want the number of solutions to

• $$~x_1 + x_2 + x_3 + x_4 + x_5 = 17.$$

• $$~x_1, ~x_2, ~x_3, ~x_4, ~x_5 \in \Bbb{Z_{\geq 1}}.$$

• $$~x_1, ~x_2, ~x_3, ~x_4, ~x_5 \in \Bbb{Z_{\leq 9}}.$$

Stars and Bars theory is based on the lower bound being $$~0,~$$ rather than $$~1.$$ So, first, use the change of variable
$$~y_i = x_i - 1 ~: ~i \in \{1,2,3,4,5\}.~$$

So, now you want the number of solutions to

• $$~y_1 + y_2 + y_3 + y_4 + y_5 = 17 - 5 = 12.$$

• $$~y_1, ~y_2, ~y_3, ~y_4, ~y_5 \in \Bbb{Z_{\geq 0}}.$$

• $$~y_1, ~y_2, ~y_3, ~y_4, ~y_5 \in \Bbb{Z_{\leq 8}}.$$

Let $$~S~$$ denote the set of all solutions, where the third bullet point above is ignored.

For $$~i \in \{1,2,3,4,5\}, ~$$ let $$~S_i~$$ denote the subset of $$~S~$$ where the specific variable $$~y_i~$$ is in violation (i.e. $$~y_i \geq 9~$$) and the the other variables may or may not be in violation.

Then, the desired computation is

$$|S| - |S_1 \cup S_2 \cdots \cup S_5|.$$

Notice that in this case, it is impossible for more than one variable to be in violation. That is, given any distinct $$~i,j \in \{1,2,3,4,5\},~$$ you must have that $$~S_i \cap S_j = \emptyset.~$$

This is because $$~(2 \times 9) > 12.$$

So, by Inclusion-Exclusion theory, and by considerations of symmetry,

$$|S| - |S_1 \cup S_2 \cdots \cup S_5| = |S| - 5|S_1|.$$

To compute $$~|S_1|,~$$ you make the further change of variable $$~z_1 = y_1 - 9.~$$

Therefore, $$~|S_1|~$$ equals the number of solutions to

• $$~z_1 + y_2 + y_3 + y_4 + y_5 = 12 - 9 = 3.$$

• $$~z_1, ~y_2, ~y_3, ~y_4, ~y_5 \in \Bbb{Z_{\geq 0}}.$$

So, By Stars and Bars Theory,

$$|S| - 5|S_1| = \binom{16}{4} - 5\binom{7}{4} = 1645.$$

Proof by brute force and dynamic programming:

[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2]
[0, 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 52, 57, 60, 61, 60, 57]
[0, 0, 0, 1, 4, 10, 20, 35, 56, 84, 120, 165, 216, 270, 324, 375, 420]
[0, 0, 0, 0, 1, 5, 15, 35, 70, 126, 210, 330, 495, 710, 976, 1290, 1645]


The $$k$$-th term on line $$n$$ is the number $$X_k^n$$ of ways to obtain sum $$k$$ with $$n$$ digits in $$1,\ldots,9$$. The induction formula is $$$$X_k^{n+1} = \sum_{i=1}^9 X_{k-i}^n$$$$ The table shows that $$X_{17}^5 = 1645$$

@Amritraj Lamba: Hi welcome to MSE. You can turn the problem into an equation like below $$\overline{abcde} \to a+b+c+d+e =17$$ but some conditions are missed here, what conditions? $$1\leq a,b,c,d,e \leq 9$$ then ude combinatorics to find the numbers of solutions. $$(a-1)+(b-1)+(c-1)+(d-1)+(e-1)=17-5 \\a'+b'+c'+d'+e'=12\\ {{14+5-1}\choose {5-1}}-5{2+5-1 \choose 5-1}$$

• The conditions are $1\le a, b, c, d, e\le 9$ Dec 30, 2023 at 15:07
• Oh thanks, I fixed it. Dec 30, 2023 at 15:17
• Python gives $\binom{18}{4} - 5 \binom{6}{4}=2985$ which is not the correct result $1645$. Dec 30, 2023 at 16:02