# solving combinatorial problem using partition functions

How many natural numbers less than 99000 have the sum of the digits equal to 8.

This is what I tried to do.Let $x_i$ be the ith digit for any $i \in \{1,2,3,4,5\}$. Ways of creating numbers less than 99000 are
case 1: starting from 8.
$$x_1\le8,x_2\le9,x_3\le9,x_4\le9,x_5\le9$$

case 2 : starting from 9, when $x_1=9$. But in this case $x_1=9$ already violates the condition that sum of the digits is equal to 8 .Therefore we can ignore this case.

Therefore the problem is equivalent to the number of integer solutions to

$$x_1+x_2+x_3+x_4+x_5=8$$

subject to

$$0<x_1\le8,0<x_2\le9,0<x_3\le9,0<x_4\le9,0<x_5\le9.$$

(Since natural numbers)

I know how to do this if the condition was only $x_1\le8,x_2\le9,x_3\le9,x_4\le9,x_5\le9$

That is consider no restriction solutions and subtract from it the solutions with conditions $x_1\ge10,x_2\ge10,\ldots,x_5\ge10$

But with greater than zero condition what should I do ?

• Why $\gt 0$?. Numbers $80000, 8000, 800, 80, 8$, for example, should all be counted, shouldn't they? – Mick A Oct 11 '14 at 16:02
• @MickA Because it says how many natural numbers numbers like 800 can't be included right – clarkson Oct 11 '14 at 17:00
• By what definition are numbers like $800$ not natural numbers? – Semiclassical Oct 11 '14 at 17:02
• What I thought was that $x_i$th digit has to be natural and sum of $x_i$'s has to be 8 – clarkson Oct 11 '14 at 17:05
• I don't see that restriction in the question as you've written it. (Had they said "using nonzero digits" I'd agree.) Plus it would give the strange situation of $800$ being one less than a natural number, one more than a natural number, and nevertheless not natural. – Semiclassical Oct 11 '14 at 17:08

Before we get to your question, we need to fix your setup: as others have pointed out in the comments, your limits on the $x_k$ incorrectly exclude solutions with $0$s, like $800$ and $710$. In fact you want $0\le x_k\le 8$ for $k=1,2,3,4,5$: $0$ should be allowed in any position, and there’s no need to allow $9$ in any position, since a $9$ would make the sum too big. Thus, you want the number of integer solutions to the equation

$$x_1+x_2+x_3+x_4+x_5=8\tag{1}$$

subject to the condition that $0\le x_k\le 8$ for $k=1,2,3,4,5$. Thus, the difficulty that you asked about doesn’t actually arise in this problem.

If your bounds on the $x_k$ were correct, you could solve the problem as follows. For $k=1,2,3,4,5$ let $y_k=x_k-1$; then $(1)$ holds if and only if

$$y_1+y_2+y_3+y_4+y_4=3\;,$$

and the $y_k$’s satisfy $x_1\le 7$ and $x_k\le 8$ for $k=2,3,4,5$.

• Thanks for the answer.The number of integer solutions I get is 495. I've made a mess in understanding the part of "natural numbers" – clarkson Oct 12 '14 at 6:40
• @clarkson: You’re welcome. $495=\binom{8+5-1}{5-1}$ is right. As far as the term natural number goes, you have to be a little careful: many mathematicians — I’m one — use it to mean non-negative integer, but there are also quite a few who use it to mean positive integer. In this case it doesn’t matter which convention is in use, since the integer $0$ doesn’t have digit sum $8$ anyway. – Brian M. Scott Oct 12 '14 at 6:43