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.

  • 0
    Did you try to calculate some values and ask [OEIS](http://oeis.org/)?2012-04-23
  • 4
    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: http://en.wikipedia.org/wiki/Vandermonde's_identity2012-04-23
  • 0
    @draks: I have just tried with the case of $k=3$ and had this http://oeis.org/A002893: $f(n,3) = \sum_{i=0}^n \binom{n}{i}^2 \binom{2i}{i}$.2012-04-23
  • 0
    @Yuan: Thank you for the link to the Generalized Vandermonde's identity. But I think it doesn't work here.2012-04-23
  • 2
    @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](http://en.wikipedia.org/wiki/Rothe%E2%80%93Hagen_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.2012-04-23
  • 0
    @joriki: Sorry I don't make it clear: "it" is the identity and "here" is the question. By the way, thank for your advice.2012-04-23
  • 1
    @Vincent: You can get equation tags right-aligned using e.g. `\tag 6`. That gets them out of the way of the equations themselves.2012-04-24

2 Answers 2