Prove a combinatorial identity: $ \sum_{n_1+\dots+n_m=n} \prod_{i=1}^m \frac{1}{n_i}\binom{2n_i}{n_i-1}=\frac{m}{n}\binom{2n}{n-m}$

Question

Prove the combinatorial identity $$ \sum_{n_1+\ldots+n_m=n} \;\; \prod_{i=1}^m \frac{1}{n_i}\binom{2n_i}{n_i-1}=\frac{m}{n}\binom{2n}{n-m}, \enspace n_i>0,i=1,\ldots,m $$ I "discovered" this equality during experiments with Maple, but I have no idea how to prove it. It may have a connection with Catalan numbers but that hasn't helped me.

UPDATE

Now we have brilliant proof of this equality. But may be it have purely combinatorial proof? Or proof with Catalan number's properties?

Answer 1

Using the generating function of the Catalan numbers the left is $$[z^n] \left(-1 + \frac{1-\sqrt{1-4z}}{2z}\right)^m.$$

This is $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \left(-1 + \frac{1-\sqrt{1-4z}}{2z}\right)^m \; dz.$$

Using Lagrange inversion put $1-4z=w^2$ so that $1/4-z=1/4 \times w^2$ or $z=1/4\times(1-w^2)$ and $dz = -1/2 \times w\; dw.$ This gives for the integral $$\frac{1}{2\pi i} \int_{|w-1|=\epsilon} \frac{4^{n+1}}{(1-w^2)^{n+1}} \left(-1 +\frac{1-w}{1/2\times(1-w^2)}\right)^m \times\left(-\frac{1}{2} w\right) \; dw \\ = \frac{1}{2\pi i} \int_{|w-1|=\epsilon} \frac{4^{n+1}}{(1-w^2)^{n+1}} \left(\frac{w^2-1+2-2w}{1-w^2}\right)^m \times\left(-\frac{1}{2} w\right) \; dw \\ = \frac{1}{2\pi i} \int_{|w-1|=\epsilon} \frac{4^{n+1}}{(1-w^2)^{n+1}} \frac{(w-1)^{2m}}{(1-w^2)^{m}} \times\left(-\frac{1}{2} w\right) \; dw \\ = \frac{1}{2\pi i} \int_{|w-1|=\epsilon} \frac{4^{n+1}}{(1-w^2)^{n+m+1}} (1-w)^{2m} \times\left(-\frac{1}{2} w\right) \; dw \\ = - \frac{2^{2n+1}}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(1-w)^{n+m+1}(1+w)^{n+m+1}} (1-w)^{2m} \times w\; dw \\ = - \frac{2^{2n+1}}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(1-w)^{n-m+1}(1+w)^{n+m+1}} \times w\; dw \\ = \frac{(-1)^{n-m} 2^{2n+1}}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(w-1)^{n-m+1}(1+w)^{n+m+1}} \times w\; dw.$$

The integral has two pieces, the first is $$\frac{(-1)^{n-m} 2^{2n+1}}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(w-1)^{n-m}(2+w-1)^{n+m+1}} \; dw \\ = \frac{(-1)^{n-m} 2^{n-m}}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(w-1)^{n-m}(1+(w-1)/2)^{n+m+1}} \; dw.$$

This is $$(-1)^{n-m} 2^{n-m} (-1)^{n-m-1} {n-m-1+n+m\choose n+m}\frac{1}{2^{n-m-1}} = -2{2n-1\choose n+m}.$$

The second piece is $$\frac{(-1)^{n-m} 2^{2n+1}}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(w-1)^{n-m+1}(2+w-1)^{n+m+1}} \; dw \\ = \frac{(-1)^{n-m} 2^{n-m}}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(w-1)^{n-m+1}(1+(w-1)/2)^{n+m+1}} \; dw.$$

This is $$(-1)^{n-m} 2^{n-m} (-1)^{n-m} {n-m+n+m\choose n+m}\frac{1}{2^{n-m}} = {2n\choose n+m}.$$

Collecting the two pieces we obtain $${2n\choose n+m} -2{2n-1\choose n+m} = {2n\choose n+m} - 2\frac{n-m}{2n}{2n\choose n+m} \\= \frac{2n-2n+2m}{2n}{2n\choose n-m} = \frac{m}{n}{2n\choose n-m}.$$

Answer 2

Since $$ \sum_{n\geq 1}\frac{1}{n}\binom{2n}{n-1}x^n = -1+\frac{1-\sqrt{1-4x}}{2x}=\frac{1-\sqrt{1-4x}}{1+\sqrt{1+4x}}\tag{1}$$ the LHS is just the coefficient of $x^n$ in the Taylor series of $$ f(x) = \left(\frac{1-\sqrt{1-4x}}{1+\sqrt{1+4x}}\right)^m \tag{2}$$ that can be computed by using Chebyshev polynomials or the Lagrange inversion theorem, since the inverse function of $\frac{1-\sqrt{1-4x}}{1+\sqrt{1+4x}}$ is just $\frac{y(1-y^2)}{(1+y^2)^2}$.

Answer 3

We will consider the "circle of pairs" ${CP}_k$, more precisely, ${CP}_k:=\mathbb{Z}_k\times\{1,2\}$, where $k$ is some positive integer and $\mathbb{Z}_k$ is the additive cyclic group as usual.

A colouring of ${CP}_k$ is a function $f:{CP}_k\rightarrow\{0,1\}$. The size of a colouring $f$ is defined as $|f^{-1}(1)|$. Two colourings $f,g$ of ${CP}_k$ (of the same size) can be the same "by rotation", more precisely, there exists $a\in\mathbb{Z}_k$ such that $f((x+a,i))=g((x,i))$ for all $\{x,i\}\in{CP}_k$.

Note that the left hand side of the identity is exactly the number of ways to have colouring of $m$ linearly ordered circle of pairs ${CP}_{n_1},\dots,{CP}_{n_m}$ of sizes $n_1-1,\dots,n_m-1$ respectively for $n_1,\dots,n_m>0$ with $n_1+\dots+n_m=n$ up to rotation.

Before we show the right hand side of the identity is also this number, we take a more detailed look into a colouring. Let $f$ be a colouring of ${CP}_k$ of size $l$ for some $l<k$. For $x\in\mathbb{Z}_k$, we denote the pair $\{(x,1),(x,2)\}$ by $P_x$. Note that for each $x\in\mathbb{Z}_k$, $f(P_x)$ can be $\{0,1\}$, $\{0\}$ or $\{1\}$.

We now partition the pairs into $4$ types:

(i) For each $x\in\mathbb{Z}_k$, $P_x$ is of Type I if $f(P_x)=\{0,1\}$;

(ii) For each $x\in\mathbb{Z}_k$, $P_x$ is of Type II if $f(P_x)=\{1\}$;

(iii) Pairs Type III are defined in a way that each of them is one-to-one corresponded with one pair of Type II: Firstly, we mark all pairs of Type I and II. Then, for each pair $P_y$ of Type II, find the smallest $a\in\{1,\dots,k\}$ with that $P_{x+a}$ is still not marked yet, this pair $P_{x+a}$ must satisfy $f(P_{x+a})=\{0\}$, mark $P_{x+a}$;

(iv) For $x\in\mathbb{Z}_k$, $P_x$ is of Type IV if it is neither of Type I, II nor III.

The main observations are, given a colouring of ${CP}_k$ of size $l<k$, (a) although in (iii) we can pick pairs of Type II in several different orders, but it does not alter which type a pair will be assigned; (b) the total number of pairs of Types I, II and III is $l$, and the number of pairs of Type IV is $k-l$. For example, with given a colouring of ${CP}_{n_1}$ of size $n_1-1$, there is exactly one pair of Type IV and it is uniquely determined.

Back to our problem, we take a colouring $f$ of ${CP}_n$ of size $n-m$ (up to rotation). In this colouring we have exactly $m$ pairs $P_{x_1},\dots,P_{x_m}$ of Type IV. We pick one pair $P_{x_j}$ amongst these $m$ pairs. You may notice that we can have $\frac m n \binom{2n}{n-m}$ ways to do it. We now cut ${CP}_n$ into $m$ segments, namely $\{P_{x_1},\dots,P_{x_2-1}\},\{P_{x_2},\dots,P_{x_3-1}\},\dots,\{P_{x_m},\dots,P_{x_1-1}\}$, and glue them into $m$ circle of pairs in a natural way. We order the circle of pairs containing $P_{x_j}$ as the first circle of pairs, the circle of pairs containing $P_{x_{j+1}}$ as the second circle of pairs, and so on. And please excuse me for leaving the tedious detail of showing that this process does provide us a one-to-one correspondence :)