Dtyjlui

Find the value of $$mathop{sumsum}_{0leq i<jleq 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+2mathop{sumsum}_{0leq i<jleq 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)^ncdot (x+1)^n = (1+x)^{2n} = binom{2n}{n}$$

So we get $$mathop{sumsum}_{0leq i<jleq n}binom{n}{i}cdot binom{n}{j} = frac{1}{2}left[2^{2n} - binom{2n}{n}right]$$

Thanks

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 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.