4
$\begingroup$

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.

  • 1
    @Vincent: You can get equation tags right-aligned using e.g. `\tag 6`. That gets them out o$f$ the way o$f$ the equations themselves.2012-04-24

2 Answers 2

5

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
    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.2012-04-24
3

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} $