3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Really sloppy to write $(1+x)^{2n}=\binom{2n}{n}$. $\endgroup$ – Thomas Andrews Feb 27 '16 at 17:35
  • $\begingroup$ 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. $\endgroup$ – Friedrich Philipp Feb 27 '16 at 17:36
  • $\begingroup$ Mixed terms? @FriedrichPhilipp $\endgroup$ – Thomas Andrews Feb 27 '16 at 17:36
  • $\begingroup$ 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? $\endgroup$ – Thomas Andrews Feb 27 '16 at 17:39
  • $\begingroup$ @Thomas Andrews: Yes. In $(1+x)^n(1+x)^n$. But I edited my comment. $\endgroup$ – Friedrich Philipp Feb 27 '16 at 17:39
3
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ 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$. $\endgroup$ – Thomas Andrews Feb 27 '16 at 17:44
  • 2
    $\begingroup$ 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. $\endgroup$ – André Nicolas Feb 27 '16 at 17:48
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.