# Combinatorics - An unproved slight generalization of a familiar combinatorial identity

One of the most basic and famous combinatorial identites is that

$$\sum_{i=0}^n \binom{n}{i} = 2^n \; \forall n \in \mathbb{Z^+} \tag 1$$

There are several ways to make generalizations of $(1)$, one is that:

Rewrite $(1)$: $$\sum_{a_1,a_2 \in \mathbb{N}; \; a_1+a_2=n} \frac{n!}{a_1! a_2!} = 2^n \; \forall n \in \mathbb{Z^+} \tag 2$$

Generalize $(2)$: $$\sum_{a_1,...,a_k \in \mathbb{N}; \; a_1+...+a_k=n} \frac{n!}{a_1!...a_k!} = k^n \; \forall n,k \in \mathbb{Z^+} \tag 3$$

Using Double counting, it is easy to prove that $(3)$ is true. So we have a generalization of $(1)$.

The question is whether we can generalize the identity below using the same idea

$$\sum_{i=0}^n \binom{n}{i}^2 = \binom{2n}{n} \; \forall n \in \mathbb{Z^+} \tag 4$$

which means to find $f$ in

$$\sum_{a_1,...,a_k \in \mathbb{N}; \; a_1+...+a_k=n} \left ( \frac{n!}{a_1!...a_k!} \right )^2 = f(n,k) \; \forall n,k \in \mathbb{Z^+} \tag 5$$

That is the problem I try to solve few days now but not achieve anything. Anyone has any ideas, please share. Thank you.

P.S: It is not an assignment, and sorry for my bad English.

Supplement 1: I think I need to make it clear: The problem I suggested is about to find $f$ which satisfies $(5)$. I also show the way I find the problem, and the only purpose of which is that it may provide ideas for solving.

Supplement 2: I think I have proved the identity of $f(n,3)$ in the comment below $$f(n,3) = \sum_{i=0}^n \binom{n}{i}^2 \binom{2i}{i} \tag 6$$ by using Double Counting:

We double-count the number of ways to choose a sex-equal subgroup, half of which are on the special duty, from the group which includes $n$ men and $n$ women (the empty subgroup is counted).

The first way of counting: The number of satisfying subgroups which contain $2i$ people is $\binom{n}{i}^2 \binom{2i}{i}$. So we have the number of satisfying subgroups is $RHS(6)$.

The second way of counting: The number of satisfying subgroups which contain $2(a_2+a_3)$ people, $a_2$ women on the duty and $a_3$ men on the duty is $$\left ( \frac{n!}{a_1!a_2!a_3!} \right )^2$$. So the number of satisfying subgroups is $LHS(6)$.

Hence, $(6)$ is proved.

• Did you try to calculate some values and ask OEIS? – draks ... Apr 23 '12 at 14:27
• The square in the identity is a red herring; it becomes much easier to understand when you write it as $\sum_i {n \choose i} {n \choose n-i} = {2n \choose n}$, and then the appropriate generalization is Vandermonde's identity: en.wikipedia.org/wiki/Vandermonde's_identity – Qiaochu Yuan Apr 23 '12 at 15:15
• @draks: I have just tried with the case of $k=3$ and had this oeis.org/A002893: $f(n,3) = \sum_{i=0}^n \binom{n}{i}^2 \binom{2i}{i}$. – Vincent J. Ruan Apr 23 '12 at 15:57
• @Vincent: What's "it"? The identity or the link? And what's "here"? Your browser or this question? By the way, Vandermonde's identity further generalizes to the Rothe-Hagen identity. Also by the way, you can get displayed equations by using double dollar signs instead of single dollar signs. They look nicer and are easier to read. – joriki Apr 23 '12 at 16:21
• @Vincent: You can get equation tags right-aligned using e.g. \tag 6. That gets them out of the way of the equations themselves. – joriki Apr 24 '12 at 11:58

I think -following the comments- that you are looking for the wrong generalization.

What you have is

$$\sum_i {n \choose i}^2= {2n \choose n}$$ which can be written as $$\sum_i {n \choose i} {n \choose n-i} = \sum_{i_1 + i_2=n}{n \choose i_1} {n \choose i_2} = {2n \choose n}$$

and the natural generalization is

$$\sum_{i_1 + i_2 + \cdots +i_k=n}{n \choose i_1} {n \choose i_2} \cdots {n \choose i_k} = {k \, n \choose n}$$

That this generalization is the "right" analogous to your first generalization is also suggested by the combinatorial interpretation.

• I think it's not about right or wrong when considering a generalization. In fact, both the generalization Qiaochu Yuan and you suggested (call it "Vandermonde generalization" from now on) and mine are just two different ways to generalize $(4)$. As you said, the Vandermonde generalization has its basis, and so is mine. – Vincent J. Ruan Apr 24 '12 at 6:41

Induction using Vandermonde's identity $$\sum_{i_1+i_2=m}\binom{n_1}{i_1}\binom{n_2}{i_2}=\binom{n_1+n_2}{m}\tag{1}$$ yields $$\sum_{i_1+i_2+\dots+i_k=m}\binom{n_1}{i_1}\binom{n_2}{i_2}\dots\binom{n_k}{i_k}=\binom{n_1+n_2+\dots+n_k}{m}\tag{2}$$