# How many positive integer solutions does the equation $a+b+c=100$ have if we require $a<b<c$?

How many positive integer solutions does the equation $a+b+c=100$ have if we require $a<b<c$?

I know how to solve the problem if it was just $a+b+c=100$ but the fact it has the restriction $a<b<c$ is throwing me off.

How would I solve this?

First we count the number of triples of positive integers $(a, b, c)$ with $a + b + c = 100$. There are $\binom{99}{2}$ of them, which results from an elementary application of stars and bars. Just line up a hundred dots, place a bar in between the $a$th and $(a +1)$th dot, and then place another bar $b$ dots to the right of the first one. Then $c$ is the number of dots to the right of the second bar. There are 99 spaces in between a hundred dots and you're choosing two of them to place bars in.

This is an overcount since it doesn't account for the condition $a < b < c$. First we should subtract the number of triples in which $a, b, c$ are not all distinct. There are 49 triples such that $a = b$: to count them, choose $x$ with $0 < x<50$, set $a = b = x$ and $c = 100-2x$. This accounts for all possible cases since if $a = b \ge 50$ then $c$ is not positive. There are also 49 triples with $a = c$, or with $b = c$, respectively. There are no triples with $a = b = c$, so the total number of triples with $a , b, c$ not all distinct is $3*49 = 147$.

The number of triples of positive integers $(a, b, c)$ with $a, b, c$ distinct and $a + b + c = 100$ is therefore $\binom{99}{2} -147$. Given a triple $(a, b, c)$ with $a< b < c$ and $a + b + c = 100$, there are six distinct ways to permute $a, b, c$, all of which our current estimate accounts for. Therefore we should divide by 6 to throw out all the triples that are in the wrong order. The final answer is $\frac{1}{6}(\binom{99}{2} -147) = 784$.

Hint: For each possible value of $a$, count the number of possible values of $b$ and $c$. It's a quite regular pattern, so you don't have to brute force much to find it.

Since $a$ is the smallest, the largest number it can be is $32$, so $a$ ranges from $1$ to $32$. The remaining sum $b+c$ must be equal to $100 - a$ and since $b$ is smaller than $c$ then $b$ ranges from $a+1$ to $\lfloor \frac{100-a}{2}\rfloor$. So for a given $a$ there are $\lfloor \frac{100-a}{2}\rfloor - a -1$ different $b$s one can choose. Therefore the possible permutations are

$$\sum_{a=1}^{32} \lfloor \frac{100-a}{2}\rfloor - a -1$$

$$=\sum_{a=1}^{32} \lfloor \frac{100-a}{2}\rfloor - \sum_{a=1}^{32}a -32$$ $$= 2\sum_{a=34}^{49}a - \sum_{a=1}^{32}a -32$$ $$=49(50) - 34(33) - \frac{32(33)}{2} -32= 768$$

EDIT:

Following the comments of Vik, it is quite clear that since we are including the case $b = a +1$ the expression should change to $$\sum_{a=1}^{32} \lfloor \frac{100-a}{2}\rfloor - a$$ However as Vik also mentioned this is an over estimate as it would also give us the combination where we have $b = c= (100-a)/2$ the case where $a$ is even. Since $b$ is strictly less than $c$, we need to remove $16$ off of our expression as there are 16 cases of when $a$ is even. Therefore, we get $$\sum_{a=1}^{32}( \lfloor \frac{100-a}{2}\rfloor - a) - 16= 784$$

• Hey, note that the range you can choose $b$ in is actually from $a + 1$ to $\lfloor{(100-a)/2} \rfloor$, inclusive of both endpoints. Therefore you shouldn't be summing $\lfloor{(100-a)/2} \rfloor - (a + 1)$: that excludes the possibility $b = a + 1$. Instead you should sum $\lfloor{(100-a)/2} \rfloor - a$. – Vik78 Apr 2 '17 at 9:25
• Also I think this is an overcount, since it includes several possibilities where $b = c$ (which occurs whenever $b = (100-a)/2$). – Vik78 Apr 2 '17 at 9:36
• Oh yes you are right my bad. I'll edit to fix this but either way I found your solution much more elegant and has a result upvoted. :) – Ziad Fakhoury Apr 2 '17 at 9:39

$a<b<c$ can be translated by $b=a+x$ and $c=b+y=a+(x+y)$, where $a,x,y>0$. $$a + b + c = 100\iff a+a+x+a+x+y=100 \iff3a+2x+y=100$$

Let $a_k$ the number of solutions of the diophantine equation $3a+2x+y=k$, where $a,x,y>0$.

$$\sum_{d=0}^\infty a_k t^k=\sum_{k=0}^\infty(\sum_{3a+2x+y=k\\a,x,y>0}t^k)=(\sum_{k=1}^\infty t^{3k})(\sum_{k=1}^\infty t^{2k})(\sum_{k=1}^\infty t^{k})=\frac{t^6}{(1-t^3)(1-t^2)(1-t)}$$

We will calculate explecitely $a_k$ now : $$\frac{t^6}{(1-t^3)(1-t^2)(1-t)}\\=\frac{t + 2}{9 (t^2 + t + 1))} - \frac{89}{72 (t - 1)} + \frac{1}{8 (t + 1)} - \frac{3}{4 (t - 1)^2} -\frac{1}{6 (t - 1)^3}-1\\=\sum_{n=1}^∞ t^n\frac{1}{72} (47 + 9 (-1)^n + 8 e^{-(2 i n π)/3} + 8 e^{(2 i n π)/3} + 6 n^2-36n)\\=\sum_{n=1}^∞ t^n\frac{1}{72} (47 + 9 (-1)^n + 16\cos(2\pi \frac{n}{3}) + 6 n^2-36n)$$

So : $$a_{100}=\frac{1}{72} (47+9 -8 +60000-3600)=784$$

By stars and bars there are ${99\choose2}$ nonnegative solutions to the equation $x_1+x_2+x_3=97$. Among these there are $3\cdot49$ having two equal $x_i\in[0\ ..\ 48]$, so that there are $${1\over6}\left({99\choose2}-3\cdot49\right)=784$$ solutions satisfying $x_1<x_2<x_3$. For each of these the numbers $a:=1+x_1$, $b:=1+x_2$, $c:=1+x_3$ form an admissible triple.