Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
4  
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

2 Answers 2

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]$$

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.