# Combination Theory Problem: Whole Numbers between 1000 and 9999 whose digits sum up to 9

Given the following problem:

How many whole numbers between 1000 and 9999 fulfill the following conditions

• The sum of it's digits is exactly 9.
• The sum of it's digits is exactly 9 and they are all different from 0.

I understand the concept of the question from which I know that I will be working with four digits and believe that I am to use the total amount of numbers between that interval which is $9999 - 1000 = 8999$.

If I am correct, it appears that the total number of possibilities will be $\binom{8999}{4}$. Would that be correct?

And how I proceed from here?

• The answer clearly is less than $9000$ and $\binom{8999}{4}$ is way larger. – Jack D'Aurizio Dec 28 '17 at 17:49
• The answer to the first point is the coefficient of $x^9$ in $$(x+x^2+\ldots+x^9)(1+x+x^2+\ldots+x^9)^3$$ and the answer to the second point is the coefficient of $x^9$ in $$(x+x^2+\ldots+x^9)^4.$$ Both instances can be solved through stars and bars – Jack D'Aurizio Dec 28 '17 at 17:50

This is a "stars and bars" problem.

https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

You have some number of digits to work with and a set of bins to distribute them across.

The digits you are free to distribute are the stars.

The separation between the bins are the bars.

a)

You must put at least 1 star in the first bin. That leaves 8 that you are free to allocate.

8 stars and 3 bars

${11\choose 3} = 165$

b) No zeros. 1 star in each bin.

5 stars 3 bars

${8\choose 3} = 56$

$$\left|\{(a,b,c,d)\in\mathbb{N}_+^4 : a+b+c+d=9\}\right|=\binom{8}{3}=56$$ and this is the answer to the second point. The answer to the first point is $$\begin{eqnarray*}&&[x^9](x+x^2+\ldots+x^9)(1+x+x^2+\ldots+x^9)^3\\&=&[x^8](1+x+x^2+\ldots+x^9)^4\\&=&[x^{12}](x+x^2+\ldots)\\&=&\left|\{(a,b,c,d)\in\mathbb{N}_+^4 : a+b+c+d=12\}\right|=\binom{11}{3}=165.\end{eqnarray*}$$

• Why is $a+b+c+d=12$ for the second part? – Omari Celestine Dec 28 '17 at 18:51
• Because the coefficient of $x^m$ in $f(x)$ equals the coefficient of $x^{m+n}$ in $x^n f(x)$ and $8+4=12$. – Jack D'Aurizio Dec 28 '17 at 18:56

Since you want a way to proceed with the problem, you wouldn’t need the total number of possibilities. Here’s where you can begin to work out the problem: The lowest number would be 1116 and the highest would be 6111 since the number can’t have any digits as 0s. After that you could list down the possibilities for every 1000 numbers that satisfy the conditions.

• This is not a very efficient approach. – Jack D'Aurizio Dec 28 '17 at 17:59
• For the first part of the question, wouldn't the highest be 9000? – Omari Celestine Dec 28 '17 at 18:47