1
$\begingroup$

Numerical calculation suggests the following two combinatorial identities: $$ \sum_{i=0}^n\sum_{j=0}^n{n\choose i}{n\choose j}{i+j\choose n}=2^n{2n\choose n},\\ \sum_{i=0}^n\sum_{j=0}^n{n\choose i}{n\choose j}{n\choose i+j}={3n\choose n}. $$ Proofs or references are all welcome.

$\endgroup$
1
$\begingroup$

For the first one: pick $i$ numbers from 1 to $n$, then $j$ numbers from $n+1$ to $2n$, then select $n$ of the $i+j$ picked numbers. One ends with an $n$-element subset of $1, \ldots, 2n$. Each such resulting subset can be generated in $2^n$ ways, once for each subset of $[1, \ldots, 2n] \setminus X$. (If $X$ is the resulting set, let $A = X\cap[1,\ldots, n]$ and $B = X \cap[n+1, \ldots, 2n]$; denote $a=|A|$ and $b=|B|$. Then $X$ can be obtained by selecting $A\cup Y$ and $B\cup Z$. There are $2^{n-a}$ ways for $Y$ and $2^{n-b}$ ways for $Z$, hence $2^{n-a}2^{n-b} = 2^n$ ways for $X$.)

For the second one: $\binom{3n}{n}$ is the number of ways to pick $n$ numbers from $1, 2, \ldots, 3n$. You can pick $i$ from the first $n$, $j$ from the next $n$, and are left to pick $n-(i+j)$ from the last $n$ (or to ignore $i+j$ from the last $n$). The last factor is 0 if you have already picked more than $n$ from the first two buckets.

$\endgroup$
  • $\begingroup$ Very nice proofs! $\endgroup$ – Ji-Cai Liu May 17 '17 at 14:54
1
$\begingroup$

I do not have the complete proof but still here is something interesting for the first identity $\sum_{i=0}^n\sum_{j=0}^n{n\choose i}{n\choose j}{i+j\choose n} = \sum_{s=0}^{2n}\sum\limits_{i+j=s}{n\choose i}{n\choose j}{i+j\choose n}=\sum_{s=0}^{2n}{s\choose n}\sum\limits_{i+j=s}{n\choose i}{n\choose j}$ and the internal sum can be written $\sum\limits_{i+j=s}{n\choose i}{n\choose j}=\sum_{k=0}^s{n \choose k}{n \choose s-k} \stackrel{Vandermonde \ identity}{=} {2n \choose s}$ therefore $\sum_{i=0}^n\sum_{j=0}^n{n\choose i}{n\choose j}{i+j\choose n} = \sum_{s=0}^{2n}{s \choose n}{2n \choose s}$

$\endgroup$
  • $\begingroup$ I follows you results. $\sum_{s=0}^{2n}{s\choose n}{2s\choose n}={2n\choose n}\sum_{s=0}^{2n}{n\choose 2n-s}={2n\choose n}2^n$. This completes the proof of the first identity. $\endgroup$ – Ji-Cai Liu May 17 '17 at 14:51
  • $\begingroup$ Using your method, the second one can also be proved by the Chu-Vandermonde identity. Thanks! $\endgroup$ – Ji-Cai Liu May 17 '17 at 15:00

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.