# Number of solutions, $a+b+c=n$, $a\gt b\gt c\ge0$

Number of non negative integral solutions for $a + b + c = n$
Where $n$ is a positive integer are
$$\binom{n + 3 - 1}{3 - 1}$$

But if a condition is there $a > b > c$
Is there any direct method by which we can find out required number of solutions.

I believe that we should multiply original number of solutions by $1 / 4$ as there are four following cases possible $a = b > c$
$a = b = c$
$a > b = c$
$a > b > c$

-
Dividing by 4 would be appropriate only if the cases were equal in number and if you already had $a \ge b \ge c$. When $n$ is large, there should be many more solutions with $a,b,c$ all different than solutions with some equal. There are also cases with $c \gt b \gt a$, for example. Better to find the number of solutions with $a,b,c$ all different. Then you can divide by $6$ because there are that many orders of $a,b,c$ – Ross Millikan Jul 4 '12 at 15:39
What if I give you a equation a + b + c = n where a >= b > = c – Arpit Bajpai Jul 4 '12 at 15:55
Is there any method to find number of solutions to original question. – Arpit Bajpai Jul 4 '12 at 15:56
I just removed the linear-algebra tag, it doesn't seem to be relevant. – Ben Millwood Jul 4 '12 at 16:34

When $c=0$, there are $[(n-1)/2]$ solutions, since $b$ can be any positive integer not exceeding $(n-1)/2$.

When $c\ne0$, let $d=a-c$, $e=b-c$, then $d\gt e\gt0$ and $d+e=n-3c$, so the number of solutions (by the previous argument) is $[(n-3c-1)/2]$.

$c$ can be anything from 0 to $[n/3]-1$, so the answer is $$f(n)=\sum_{c=0}^m\left[{n-3c-1\over2}\right]$$ where $m=[n/3]-1$. Now we need a closed form for $f(n)$. Here's one way to go. Note $$f(n+6)=\sum_{c=-2}^{m}\left[{n-3c-1\over2}\right],\qquad f(n+12)=\sum_{c=-4}^{m}\left[{n-3c-1\over2}\right]$$ so $$f(n+12)-2f(n+6)+f(n)=\left[{n+11\over2}\right]+\left[{n+8\over2}\right]-\left[{n+5\over2}\right]-\left[{n+2\over2}\right]=6$$ Thus on any arithmetic progression with common difference 6, $f(n)$ is a quadratic polynomial. So we just have to find the 6 quadratics.

We calculate $f(3)=1$, $f(9)=7$, $f(15)=19$, so (by standard techniques) $f(6n+3)=3n^2+3n+1$; the whole deal looks like this: \eqalign{f(6n)&=3n^2\cr f(6n+1)&=3n^2+n\cr f(6n+2)&=3n^2+2n\cr f(6n+3)&=3n^2+3n+1\cr f(6n+4)&=3n^2+4n+1\cr f(6n+5)&=3n^2+5n+2\cr} A simpler formula is $$f(n)=\left[{n^2+6\over12}\right]$$

-

You have the total number of solutions. Let's first count the number of solutions in which we do not have all three of $a$, $b$, $c$ pairwise distinct. We'll take them out directly before figuring out our overcount.

How many solutions are there with at least two of the numbers equal? Say $a=b=k$. Then we must have $2k\leq n$, or $k\leq \lfloor\frac{n}{2}\rfloor$. Once you have that equal value, the third variable has only one possibility.

So you have $\lfloor\frac{n}{2}\rfloor+1$ such solutions (to include $0$); then you get to choose the "odd man out" in $3$ different ways. So we have $3\lfloor\frac{n}{2}\rfloor+3$ possibilities. However, you have overcounted a solution with $a=b=c$ if there is one; there is one if and only if $n\equiv 0\pmod{3}$. So the number of solutions with at least two of the numbers equal is \begin{align*} 3\left\lfloor\frac{n}{2}\right\rfloor+1&\qquad\text{if }n\equiv 0\pmod{3}\\ 3\left\lfloor\frac{n}{2}\right\rfloor+3 &\qquad\text{otherwise.} \end{align*}

For example, take $n=11$. The solutions with duplicates have $(0,0,11)$, $(1,1,9)$, $(2,2,7)$, $(3,3,5)$, $(4,4,3)$, and $(5,5,1)$, and each of them can be assigned to $a$, $b$, and $c$ in three different ways. This gives 18 solutions; $\lfloor\frac{n}{2}\rfloor = \lfloor\frac{11}{2}\rfloor = 5$, and since $11$ is not divisible by $3$, the formula gives $3(5)+3 = 18$.

Now say $n=15$; according to our formula, we should get $3\lfloor\frac{15}{2}\rfloor + 1 = 22$ solutions. What are they? There are three solutions for each of the following multiset of values: $(0,0,15)$, $(1,1,13)$, $(2,2,11)$, $(3,3,9)$, $(4,4,7)$, $(6,6,3)$, and $(7,7,1)$; and then there is one solution with $a=b=c=5$. Total: 22 solutions.

Okay, so now we know how many solutions have at least one equal sign. If we take them out of the total solutions, then we are left with only solutions in which $a$, $b$, and $c$ are all distinct. For each set of values that yield $n$, there are $3!=6$ ways of "distributing" the values among $a$, $b$, and $c$. So if we divide the number we have by $6$, we will get the answer you seek.

In summary, we get: \begin{align*} \frac{1}{6}\left(\binom{n+2}{2} - 3\left\lfloor\frac{n}{2}\right\rfloor -1\right) &\qquad\text{if }n\equiv 0\pmod{3}\\ \frac{1}{6}\left(\binom{n+2}{2} - 3\left\lfloor\frac{n}{2}\right\rfloor -3\right) &\qquad\text{otherwise.} \end{align*}

Let's test the formula. If $n=11$, then the solutions with $a\gt b \gt c\geq 0$ are: $(10,1,0)$, $(9,2,0)$, $(8,3,0)$, $(7,4,0)$, $(6,5,0)$, $(8,2,1)$, $(7,3,1)$, $(6,4,1)$, $(6,3,2)$, and $(5,4,2)$. That's it, because if $c=3$, then we would neeed $b\geq 4$ and $a\geq 5$, and that's already too much. So we get a total of ten solutions. According to the formula we found above, we should have $$\frac{1}{6}\left(\binom{13}{2} - 3\left\lfloor\frac{11}{2}\right\rfloor -3\right) = \frac{1}{6}(78 - 15-3)=\frac{60}{6} = 10.$$ Good.

Now, if $n=15$, the solutions with $a\gt b\gt c\geq 0$ are: $(14,1,0)$, $(13,2,0)$, $(12,3,0)$, $(11,4,0)$, $(10,5,0)$, $(9,6,0)$, $(8,7,0)$, $(12,2,1)$, $(11,3,1)$, $(10,4,1)$, $(9,5,1)$, $(8,6,1)$, $(10,3,2)$, $(9,4,2)$, $(8,5,2)$, $(7,6,2)$, $(8,4,3)$, $(7,5,3)$, and $(6,5,4)$; a total of 19 solutions. According to the formula, we have: $$\frac{1}{6}\left(\binom{17}{2}-3\left\lfloor\frac{15}{2}\right\rfloor -1\right) = \frac{1}{6}(136 - 21 -1) = \frac{114}{6} = 19.$$

Well, looks right, at any rate...

To count the number of solutions with $a\geq b\geq c$, we can take the total above for those with $a\gt b\gt c$. Then we add one for each solution with at least two numbers equal, namely $\lfloor\frac{n}{2}\rfloor+1$ solutions.

-