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.

  • $\begingroup$ Did you try to calculate some values and ask OEIS? $\endgroup$ – draks ... Apr 23 '12 at 14:27
  • 4
    $\begingroup$ 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 $\endgroup$ – Qiaochu Yuan Apr 23 '12 at 15:15
  • $\begingroup$ @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}$. $\endgroup$ – Vincent J. Ruan Apr 23 '12 at 15:57
  • 2
    $\begingroup$ @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. $\endgroup$ – joriki Apr 23 '12 at 16:21
  • 1
    $\begingroup$ @Vincent: You can get equation tags right-aligned using e.g. \tag 6. That gets them out of the way of the equations themselves. $\endgroup$ – 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.

  • 1
    $\begingroup$ 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. $\endgroup$ – 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} $$


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.