# $100$ can be divided into the sum of several numbers. How many different possibilities are there?

$100$ can be divided into the sum of several numbers as $1+99$ or $1+1+98$, and we set all the numbers have to be positive. Besides, $1+99$ is different from $99+1$. How many different possibilities are there?

I start to divide $100$ into the sum of two numbers. There are 99 possibilities.

Then divide $100$ into the sum of three numbers. There are $98+97+\dots+1$ possibilities.

Then divide $100$ into the sum of four numbers. For example $1+a+b+c=100$. Then there are $97+96+\dots+1$ ways to write $a,b,c$. For $2+a'+b'+c'=100$, there are $96+95+\dots+1$ ways to write $a',b',c'$.

However I don't think this approach is promising. Is there any feasible way to solve this problem?

## 1 Answer

There are $\binom{n-1}{r-1}$ integer solutions $(x_1 ,\ldots, x_r)$, all $\ge 1$ to $x_1 + x_2 + \ldots x_r =n$ , see here, e.g.

You want this for all $r=1,\dots 100$, just sum these:

$$\sum_{r=1}^{100} \binom{99}{r-1} = 2^{99}$$

I think the following combinatorial argument works: write $100 = 1 + \ldots + 1$, now we can either leave or delete one of the 99 $+$-signs ((and when deleting combine the numbers on both sides): e.g. for $n=3 = 1 + 1 + 1$, deleting none leaves 3 =1 + 1 +1 , deleting the first + leaves 3 = 2 + 1, deleting the second 1+2, deleting all leaves 3 = 3, etc., so $2^2$ solutions in all, if you don't want the last trivial one, subtract 1 from my answer. )

• The combinatorial argument uses the technique known as stars and bars; more can be found on its wikipage here. – Benjamin Dickman Mar 26 '17 at 9:33
• @BenjaminDickman The first one does, my reasoning for the final answer does not use this technique. – Henno Brandsma Mar 26 '17 at 11:29