# Counting the numbers with certain sum of digits.

The question :

In how many different numbers between $1$ and $100000000$ have the sum of their digits equal to $45$?

I'm thinking about using the stars and bars formula but I'm not sure if it's possible and how.

• an integer represented by $a_1a_2a_3a_4a_5a_6a_7a_8$ ignoring the upper bound for obvious reasons..satisfies this $$\sum_{i=1}^{8}a_j = 45$$? – Chinny84 Jan 29 '15 at 15:36
• – MJD Jan 29 '15 at 15:59

You can use inclusion exclusion to get the answer 2706880. First let's reformulate the problem. We need to find the number of non-negative integer solutions to

$$x_1 \, + \, x_2 \, + \; ... \; + \, x_k = n \;\;\;\;\;\;\;\;\;\; (*)$$

where $$x_i < \mu$$. If we can solve this, then we can simply plug in $$n=45, k=8$$ and $$\mu=10$$ to solve your problem. Each $$x_i$$ represents the $$i$$'th digit of a given number between $$0$$ and $$10^k$$. Now if we don't have the restriction that $$x_i<\mu$$, then the solutions are known as weak compositions, and the number of such weak compositions is easily seen to be $${ n+k-1 \choose k-1}$$ using stars and bars

To handle the constraint $$x_i < \mu$$ we can use the principle of inclusion-exclusion which goes as follows: Let $$S$$ be a set of objects, let $$A,B,C$$ be subsets of $$S$$ that satisfy properties $$a,b,c$$, respectively. Suppose we want to find the number of elements that don't satisfy any of the properties $$a,b$$, or $$c$$. That is, we want to count $$|S - (A \cup B \cup C)|$$ or the shaded part in the following diagram.

$$\qquad \qquad \qquad \qquad \qquad \qquad \qquad$$

We can count this by sieving

$$|S| \; - \; (|A|+|B|+|C|) \; + \; \left( |A \cap B|+|A \cap C|+|B \cap C| \right) \; - \;|A \cap B \cap C|$$

$$\qquad \qquad \qquad \quad$$

This is easily generalized for $$k$$ different properties. Going back to your problem, we let $$S$$ be the set of all solutions to (*) and let $$P_i$$ be the subset where $$x_i \geq \mu$$. Then we want to count

$$\left|S - (P_1 \cup P_2 \, \cup \; ... \; \cup \, P_k \right)| = \left| \, S \, \right| - \sum_i\, \left|P_i\right| \; + \; \sum_{i,j} \left |P_i \cap P_j \right| \; - \;\; ...$$

But what are the summands? Or specifically, what is $$|P_i|$$? Solutions in $$P_i$$ are solutions to the new problem

$$\begin{array} \; & x_1 \, + \, x_2 \, + \; ... \; +&(x_i)_{\geq\mu} &+ \; ... \; + \, x_k &= n \\ \leadsto & x_1 \, + \, x_2 \, + \; ... \; + &(\mu+x_i') &+ \; ... \; + \, x_k &= n \\ \leadsto & x_1 \, + \, x_2 \, + \; ... \; + &(x_i')_{\geq 0} &+ \; ... \; + \, x_k &= n-\mu \end{array}$$

But we already know this to be $${n-\mu+k-1 \choose k-1}$$. Following a similar pattern, we notice

$$\begin{array} ( \left| S \right| &= {n+k-1 \choose k-1} \\ \left| P_i \right| &= {n+k-1-\mu \choose k-1} & \small{\;\;\;\;\; \forall \, i}\\ \left| P_i \cap P_j \right| &= {n+k-1-2\mu \choose k-1} & \small{\;\;\;\;\; \forall i,j}\\ \left| P_i \cap P_j \cap P_\ell \right| &= {n+k-1-3\mu \choose k-1} &\small{\;\;\;\;\; \forall \, i,j,k}\\ &... \end{array}$$

So our desired sum becomes

$$\begin{array} (\displaystyle \left|S - (P_1 \cup P_2 \, \cup \; ... \; \cup \, P_k) \right| & = \left| \, S \, \right| - {k \choose 1} \left|P_i\right| \; + \; {k \choose 2} \left |P_i \cap P_j \right| \; - \;\; ... \\ \\ & = \displaystyle \sum_{i=0}^{\min \{k, \lfloor n/\mu \rfloor \}} (-1)^i {k \choose i} {n+k-1-i\mu \choose k-1} \\ \end{array}$$

We truncate the sum at $$min \{k, \lfloor n/\mu \rfloor \}$$ because the summands are zero from then onward (by definition). To count the number of integers less than $$10^8$$ with digit sum $$45$$, we plug in $$n=45, k=8$$, and $$\mu=10$$ and get

$$\sum_{i=0}^4 (-1)^i {8 \choose i} {52-10i \choose 7} = 2706880$$

Yes, this is similar to a stars-and-bars problem. However, there's the extra constraint that each digit be at most nine. Therefore, your problem is equivalent to this one (with $k=45$, $n=8$ and $c=9$). For the answer in that question given as a sum of $n=8$ terms, Maple gives 2,706,880 numbers between 1 and 100,000,000 whose digits have a sum of 45.

As an alternative noted in the comments, you can approximate this result with the central limit theorem. You can think of each digit as a random variable uniformly distributed between 0 and 9 (with mean $\frac92$ and standard deviation $\frac{\sqrt{33}}2$). Then, by the central limit theorem, the sum $S$ of the digits in an eight-digit number would have a distribution that is approximately normal (with a mean of $8\cdot\frac92$ and standard deviation $\frac{\sqrt{8\cdot33}}2$). Using this normal distribution, $\text{prob}(44.5<S<45.5)\approx 0.0266$, so we get an approximation of $100,000,000\cdot0.0266=2,660,000$ numbers satisfying your condition.