# >The value of $\mathop{\sum\sum}_{0\leq i<j\leq n}\binom{n}{i}\cdot \binom{n}{j}$

Find the value of $$\mathop{\sum\sum}_{0\leq i<j\leq n}\binom{n}{i}\cdot \binom{n}{j}$$

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

• Really sloppy to write $(1+x)^{2n}=\binom{2n}{n}$. – Thomas Andrews Feb 27 '16 at 17:35
• I don't agree on how you obtain $\binom{2n}{n}$. What did you do with the mixed terms? EDIT: Now, I see what you did. You only look at the coefficients for $x^n$. Nice. – Friedrich Philipp Feb 27 '16 at 17:36
• Mixed terms? @FriedrichPhilipp – Thomas Andrews Feb 27 '16 at 17:36
• Why don't you ask up front for a combinatorial proof, if that is your main question, rather than forcing answerers to read a non-combinatorial proof? – Thomas Andrews Feb 27 '16 at 17:39
• @Thomas Andrews: Yes. In $(1+x)^n(1+x)^n$. But I edited my comment. – Friedrich Philipp Feb 27 '16 at 17:39

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?

• The last can be rewritten $\sum \binom{n}{i}\binom{n}{n-i}$ and the terms represent the number of ways to choose $i$ elements from $A$ and $n-i$ elements from $B$, which, when summed, is the number of ways to choose $n$ elements from $A\cup B$. – Thomas Andrews Feb 27 '16 at 17:44
• How many ways to choose $n$ people from $n$ boys and $n$ girls? For every decision about which $i$ boys we will pick, there are $\binom{n}{i}$ ways to decide which girls we will not pick. – André Nicolas Feb 27 '16 at 17:48

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), $$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.