Demostrar una identidad combinatoria

Question

Demostrar la combinatoria de identidad $$ \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 $$ He "descubierto" esta igualdad durante los experimentos con Arce, pero no tengo idea de cómo demostrarlo. Es posible que tenga una conexión con el catalán de números, pero que no ha ayudado a mí.

ACTUALIZACIÓN

Ahora tenemos brillante prueba de esta igualdad. Pero puede ser que tenga puramente combinatoria prueba? O prueba con el catalán número de propiedades?

Answer 1

El uso de la generación de la función de la agencia catalana de los números de la izquierda es $$[z^n] \left(-1 + \frac{1-\sqrt{1-4z}}{2z}\right)^m.$$

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

El uso de Lagrange de la inversión de poner $1-4z=w^2$, de modo que $1/4-z=1/4 \times w^2$ o $z=1/4\times(1-w^2)$ $dz = -1/2 \times w\; dw.$ Esto da para la 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\ \ derecho) \; 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-2 w}{1-w^2}\right)^m \times\left(-\frac{1}{2} w\ \ derecho) \; 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\ \ derecho) \; 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\ \ derecho) \; 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\; ps.$$

La integral tiene dos partes, la primera es $$\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}} \; ps.$$

Este es $$(-1)^{n-m} 2^{n-m} (-1)^{n-m-1} {n-m-1+n+m\elegir n+m}\frac{1}{2^{n-m-1}} = -2{2n-1\elegir n+m}.$$

La segunda pieza es $$\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}} \; ps.$$

Este es $$(-1)^{n-m} 2^{n-m} (-1)^{n-m} {n-m+n+m\elegir n+m}\frac{1}{2^{n-m}} = {2n\elegir n+m}.$$

La recolección de las dos piezas obtenemos $${2n\elegir n+m} -2{2n-1\elegir n+m} = {2n\elegir n+m} - 2\frac{n-m}{2n}{2n\elegir n+m} \\= \frac{2n-2n+2m}{2n}{2n\elegir n-m} = \frac{m}{n}{2n\elegir n-m}.$$

Answer 2

Desde $$ \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}$ $ la LHS es simplemente el coeficiente de $x^n$en la serie de Taylor de % de %#% $ de #% que puede ser computado usando polinomios de Chebyshev o el Teorema de inversión de Lagrange, dado que la función inversa de $$ f(x) = \left(\frac{1-\sqrt{1-4x}}{1+\sqrt{1+4x}}\right)^m \tag{2}$ es a $\frac{1-\sqrt{1-4x}}{1+\sqrt{1+4x}}$.

Answer 3

Vamos a considerar el "círculo de pares" ${CP}_k$, más precisamente, ${CP}_k:=\mathbb{Z}_k\times\{1,2\}$ donde $k$ es algún entero positivo y $\mathbb{Z}_k$ es el aditivo cíclico grupo como de costumbre.

Una coloración de ${CP}_k$ es una función de $f:{CP}_k\rightarrow\{0,1\}$. El tamaño de una coloración $f$ se define como $|f^{-1}(1)|$. Dos coloraciones $f,g$ ${CP}_k$ (del mismo tamaño) puede ser el mismo "rotación", más precisamente, existe $a\in\mathbb{Z}_k$ tal que $f((x+a,i))=g((x,i))$ todos los $\{x,i\}\in{CP}_k$.

Tenga en cuenta que el lado izquierdo de la identidad es exactamente el número de formas de coloración de $m$ linealmente ordenado círculo de pares ${CP}_{n_1},\dots,{CP}_{n_m}$ de los tamaños de las $n_1-1,\dots,n_m-1$, respectivamente, para $n_1,\dots,n_m>0$ $n_1+\dots+n_m=n$ hasta rotación.

Antes de mostrar el lado derecho de la identidad también es de este número, podemos echar un vistazo más detallado en la coloración. Deje $f$ ser una coloración de ${CP}_k$ del tamaño de la $l$ algunos $l<k$. Para $x\in\mathbb{Z}_k$, indican los par $\{(x,1),(x,2)\}$$P_x$. Tenga en cuenta que para cada $x\in\mathbb{Z}_k$, $f(P_x)$ puede ser $\{0,1\}$, $\{0\}$ o $\{1\}$.

Ahora partición de los pares en $4$ tipos de:

(i) Para cada $x\in\mathbb{Z}_k$, $P_x$ es de Tipo I si $f(P_x)=\{0,1\}$;

(ii) Para cada $x\in\mathbb{Z}_k$, $P_x$ es de Tipo II si $f(P_x)=\{1\}$;

(iii) los Pares de Tipo III se definen de manera que cada uno de ellos es uno-a-uno se correspondía con un par de Tipo II: en primer lugar, marcamos todos los pares de Tipo I y II. A continuación, para cada par de $P_y$ de Tipo II, encontrar el más pequeño de $a\in\{1,\dots,k\}$ con $P_{x+a}$ todavía no marcó, sin embargo, este par de $P_{x+a}$ debe satisfacer $f(P_{x+a})=\{0\}$, mark $P_{x+a}$;

(iv) Para $x\in\mathbb{Z}_k$, $P_x$ es de Tipo IV, si no es ni de Tipo I, II ni III.

Las principales observaciones, dada la coloración de ${CP}_k$ del tamaño de la $l<k$, (un), aunque en (iii) podemos elegir pares de Tipo II en diferentes órdenes, pero no altera la que escriba un par será asignado; (b) el número total de pares de Tipos I, II y III es $l$, y el número de pares de Tipo IV es $k-l$. Por ejemplo, con una coloración de ${CP}_{n_1}$ del tamaño de la $n_1-1$, no es exactamente un par de Tipo IV y es el único determinado.

De vuelta a nuestro problema, se toma una coloración $f$ ${CP}_n$ del tamaño de la $n-m$ (hasta rotación). En este colorante tenemos exactamente $m$ pares de $P_{x_1},\dots,P_{x_m}$ de Tipo IV. Tomamos un par $P_{x_j}$ entre estos $m$ pares. Usted puede notar que podemos tener $\frac m n \binom{2n}{n-m}$ maneras de hacerlo. Ahora nos cortan ${CP}_n$ a $m$ segmentos, a saber,$\{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}\}$, y pegarlas en $m$ círculo de pares de una manera natural. Hemos pedido el círculo de pares que contengan $P_{x_j}$ como el primer círculo de pares, el círculo de pares que contengan $P_{x_{j+1}}$ como el segundo círculo de pares, y así sucesivamente. Y por favor, discúlpame para salir de la tediosa detalle de mostrar que este proceso nos proporciona una correspondencia uno a uno :)