2
$\begingroup$

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$

  • 0
    I just removed the linear-algebra tag, it doesn't seem to be relevant.2012-07-04

2 Answers 2

5

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

1

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.