How many ways can we construct $(a,b,c,d)$ such that $a \geq b, c \geq d$ and $a+b \geq c+d$?

Question

I've been stuck on the counting problem described below for a while. I'm constructing ordered sequences of four positive integers of the form $(a,b,c,d)$, each of which are bounded above. i.e. $$a,b,c,d \in \{1,2,...,N\}$$ so that each of the variables can take on $N$ possible values. Of course, the number of lists we can form this way is $N^4$. Now, I impose that both $a\geq b$ and $c \geq d$. Since these conditions are independent, one can consider the number of ways to construct the first two elements of the list and square it. The number of ways to construct $(a,b)$ such that $a \geq b$ is simply $\frac 12 N(N+1)$, so the answer to this problem is $$\left(\frac 12 N(N+1) \right)^2=\frac 14 N^2(N+1)^2.$$ Now, where I'm getting stuck is the addition of a third constraint. This is to require that $a+b \geq c+d$, thus making the first two and last two components dependent on each other. My question is therefore: How many ordered lists of the form $(a,b,c,d)$ such that $$a,b,c,d \in \{1,2,...,N\}$$ $$a \geq b, \qquad c\geq d$$ $$a+b \geq c+d$$ are there?

Answer 1

I agree with the previous analysis. We know that the number of ways $a+b > c+d$ equals the number of ways $a+b < c+d$. We find the number of ways $a+b = c+d$, calling it $f(n)$. Then the answer to the problem is $$ \frac{\displaystyle\frac{n^2(n+1)^2}{4}-f(n)}{2} + f(n) = \frac{n^2(n+1)^2}{8} + \frac{f(n)}{2}.$$ The value of $f(n)$ depends upon the parity of $n$. If $n$ is even, $$ f_e(n) = \frac{n(2n^2+3n+4)}{12}. $$ If $n$ is odd, $$ f_o(n) = \frac{(n+1)(2n^2+n+3)}{12}. $$ The function for odd and even $n$ were reached by establishing a pattern using numbers and then using induction.