The value of $\sum_{0\le i
Find the value of
$$\sum_{0\le i<j\le n}\binom ni\binom nj$$
I get the result: $$\frac{1}{2}\left(2^{2n}-\binom{2n}{n}\right)$$ via a numeric argument.
My question is: Can we solve it using a combinational argument?
My Numeric Argument: $$\left(\sum^{n}_{r=0}\binom{n}{i}\right)^2=\sum^{n}_{r=0}\binom{n}{i}^2+2\mathop{\sum\sum}_{0\leq i<j\leq n}\binom{n}{i}\cdot \binom{n}{j}$$
So here $$\displaystyle \sum^{n}_{r=0}\binom{n}{i} = \binom{n}{0}+\binom{n}{1}+.....+\binom{n}{n} = 2^n$$
and $$\displaystyle \sum^{n}_{r=0}\binom{n}{i}^2=\binom{n}{0}^2+\binom{n}{1}^2+.....+\binom{n}{n}^2 = \binom{2n}{n}$$
above we have calculate Using $$(1+x)^n = \binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+.....+\binom{n}{n}x^n$$
and $$(x+1)^n = \binom{n}{0}x^n+\binom{n}{1}x^{n-1}+\binom{n}{2}x^{n-2}+.....+\binom{n}{n}x^0$$
Now calcualting Coefficient of $x^n$ in $$(1+x)^n\cdot (x+1)^n = (1+x)^{2n} = \binom{2n}{n}$$
So we get $$\mathop{\sum\sum}_{0\leq i<j\leq n}\binom{n}{i}\cdot \binom{n}{j} = \frac{1}{2}\left[2^{2n} - \binom{2n}{n}\right]$$
Thanks
 A: Consider two sets, $A$ and $B$ each with $n$ elements. All elements are considered distinct.
$\displaystyle \sum_{0 \leq i < j \leq n} \binom{n}{i} \binom{n}{j}$ can be interpreted as the number of ways to pick a non-empty subset of $A \cup B$ with the requirement that the number of elements from $A$ who are picked is strictly smaller than the number of elements from $B$ who are picked.
$2^{2n}$ counts the total number of ways to pick a subset of any size from $A \cup B$. The number of cases where the same number of elements are picked from $A$ and $B$ (including the empty set) is obtained from the sum $\displaystyle \sum_{i=0}^n \binom{n}{i}^2$. 
By symmetry, half of the $\displaystyle 2^{2n} - \sum_{i=0}^n \binom{n}{i}^2$ cases have more elements from $A$ compared to $B$.
The identity $\displaystyle \sum_{i=0}^n \binom{n}{i}^2 = \binom{2n}{n}$ matches the result with yours.
I do not know of a combinatorial argument for this last identity though. Does anyone have any? 
A: A bijective correspondence can be established between this issue and the following one:
[Dealing with the LHS of the equation :] 
Let $S$ be a set with Card(S)=n.
Consider all (ordered) pairs of subsets $(A,B)$ such that 
$$A \subsetneqq B \subset S. \ \ (1)$$ 
[Dealing with the RHS of the equation :] 
Consider all subsets of a set $T$ with $2n$ elements, then exclude a certain number of them (to be precised later), $T$ being defined as :
$$T:=S \cup I \ \ \ \ \text{with} \ \ \ \ \ I:=\{1,2,\cdots n\}.$$ 
Let $C$ be any subset of $T$. We are going to establish (in the "good cases") a correspondence between $C$ and an ordered pair $(A,B)$ verifying (1).
Let us define first a certain fixed ordering of the elements of $S$ :
$$a_1 < a_2 < \cdots < a_n. \ \ (2)$$
Let $B:=T \cap S$ and $J:=T \cap I$. Three cases occur :


*

*If $Card(J)<Card(B)$, $J$ is the set of indices "selecting" the elements of $B$ that belong to $A$ in the ordered set $S$.

*If $Card(J)>Card(B)$, we switch the rôles of indices and elements. This accounts for the half part of the formula: indeed this second operation will give the same sets $(A,B)$.

*If $Card(J)=Card(B)$, which happens in $2n \choose n$ cases, such cases cannot be placed in correspondence with a case considered in (1), thus have to be discarded.
I know this could be written in a more rigorous way, but I believe the main explanations are there.
