Loading [MathJax]/extensions/TeX/mathchoice.js

11 votos

Demostrando esta identidad \sum_k\frac{1}{k}\binom{2k-2}{k-1}\binom{2n-2k+1}{n-k}=\binom{2n}{n-1} usando enrejado de caminos

Cómo puedo probar la identidad de \sum_k\frac{1}{k}\binom{2k-2}{k-1}\binom{2n-2k+1}{n-k}=\binom{2n}{n-1}?

Tengo que demostrar que el uso de entramado de caminos, debe estar relacionado con el catalán números

El nth catalán número C_n cuenta el número de monotónica caminos a lo largo de los bordes de una cuadrícula con n\times n plaza de las células, que no pase por encima de la diagonal.

Ver por ejemplo este enlace

Por ejemplo, \frac{1}{k}\binom{2k-2}{k-1} es exactamente C_{k-1}, y los otros términos también puede ser expresada en términos de los números de catalán.

La segunda parte del ejercicio, pregunte a probar la fórmula de recurrencia C_n=\sum_{k=1}^n C_{k-1}C_{n-k} usando razonamiento similar (es decir, de celosía de caminos). Así que no podemos usar esta fórmula para probar la primera.

Me podrían ayudar por favor?

10voto

DiGi Puntos 1925

La derecha cuenta el número de senderos monótonos de (0,0) (n-1,n+1). Desde (n-1,n+1) está por encima de la diagonal, cada uno de estos caminos debe cruzar la diagonal en algún momento. Supongamos que el primer paso 'malo' es de (k-1,k-1) (k-1,k).

  • ¿De cuántas maneras existen de (0,0) (k-1,k-1) sin pasar por encima de la diagonal?

  • ¿De cuántas maneras existen para obtener de (k-1,k) (n-1,n+1)?

3voto

Marko Riedel Puntos 19255

Esto también se puede hacer uso de variables complejas. Supongamos que buscamos para evaluar \sum_{k=1}^n \frac{1}{k} {2k-2\elegir k-1} {2n-2k+1\elegir n-k}.

Introducir la representación integral {2n-2k+1\elegir n-k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n-2k+1}}{z^{n-k+1}} \; dz. Este tiene la propiedad de que es cero cuando k\gt n.

Obtenemos para la suma \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1}}{z^{n+1}} \sum_{k\ge 1} \frac{1}{k} {2k-2\elegir k-1} \frac{z^k}{(1+z)^{2k}} \; dz.

Recordar que la generación de la función de los números de catalán \sum_{q\ge 0} \frac{1}{p+1} {2t\elegir q} w^q = \frac{1-\sqrt{1-4w}}{2} Esto es igual a \sum_{q\ge 1} \frac{1}{q} {2q-2\choose q-1} w^{q-1} así que \sum_{q\ge 1} \frac{1}{q} {2t-2\elegir q-1} w^q = \frac{1-\sqrt{1-4w}}{2}.

Sustituir en la integral para obtener \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1}}{z^{n+1}} \frac{1-\sqrt{1-4z/(1+z)^2}}{2} \; dz.

Esto tiene dos componentes, el primero es \frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1}}{z^{n+1}} \; dz = \frac{1}{2} {2n+1\elegir n}.

El segundo es -\frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1}}{z^{n+1}} \sqrt{1-4z/(1+z)^2} \; dz \\ = -\frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} \sqrt{(1+z)^2-4z} \; dz \\ = -\frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} \sqrt{(1-z)^2} \; dz \\ = -\frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} (1-z) \; dz.

Este evalúa a \frac{1}{2} {2n\elegir n-1} - \frac{1}{2} {2n\elegir n}.

Factorización de la suma de las dos contribuciones a revelar el término de destino obtenemos \frac{1}{2} \left(\frac{2n+1}{n} + 1 - \frac{n+1}{n}\right) {2n\elegir n-1} = {2n\elegir n-1}.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X