"En la papeleta de números" se resumen en catalán números

Question

Sumar números determinados y comparar los resultados con OEIS, me encontré con que $ \sum_{k=1}^n \frac{k^2}{n} \binom{2n-k-1}{n-1} = C_{n+1} - C_{n}, $

donde $C_n$ indica el $n^{\textrm{th}}$ catalán Número. Cómo puedo probar esta ecuación? Y es allí cualquier combinatoria interpretación?

Algunos antecedentes: El número de $\frac{k}{n} \binom{2n-k-1}{n-1}$ indica el número de unranked árboles de tamaño $n$, con una raíz grado $k$ (estos números se conocen como números de boleta, ver, por ejemplo, el libro de la Analítica de la Combinatoria de Flajolet y Sedgewick, página 68). Así que uno debe tener $\sum_{k=1}^n \frac{k}{n} \binom{2n-k-1}{n-1} = C_{n}$, ya que hay $C_n$ muchos árboles de tamaño $n$.

Answer 1

Observe que: $$ \sum_{k=1}^n \frac{k^2}{n} \binom{2n-k-1}{n-1} \stackrel{k \a n+1-k}{=} \sum_{k=1}^n \frac{(n+1-k)^2}{n} \binom{n+k-2}{n-1} \stackrel{\binom{a}{b} = \binom{a}{a-b}}{=} \sum_{k=1}^n \frac{(n+1-k)^2}{n} \binom{n+k-2}{k-1} = \sum_{k=0}^{n} \frac{(n-k)^2}{n} \binom{n+k-1}{k} $$ Esto no es sino una convolución de dos secuencias de $a_{k} = \frac{k^2}{n}$$b_{k} = \binom{n+k-1}{k}$. Por lo tanto, la generación de la función de la suma de $c_n = \sum_{k=0}^{n} a_{n-k} b_k$ es el producto de las funciones de generación de $a_k$$b_k$: $$ \sum_{k=0}^\infty x^k a_k = \frac{1}{n} \sum_{k=0}^\infty x^k^2 = \frac{1}{n} \left( x\frac{\mathrm{d}}{\mathrm{d} x}\right)^2 \sum_{k=0}^\infty x^k = \frac{1}{n} \frac{x(1+x)}{(1-x)^3} $$ $$ \sum_{k=0}^\infty \binom{n+k-1}{k} x^k = \frac{1}{(1-x)^n} $$ Por lo tanto: $$ c_n = [x]^n \left( \frac{1}{n} \frac{x(1+x)}{(1-x)^3} \frac{1}{(1-x)^n} \right) = [x]^n \left( \frac{1}{n} \frac{x}{(1-x)^{n+3}} + \frac{1}{n} \frac{x^2}{(1-x)^{n+3}} \right) = \frac{1}{n} \left(\binom{2n+1}{n-1} + \binom{2n}{n-2} \right) $$ Ahora, el uso de $$ \binom{2n}{n-2} = \binom{2n+1}{n-1} - \frac{2n}{n-1} \binom{2n-1}{n-2} $$ que es fácilmente demostrado el uso de la recurrencia de la relación para factoriales que comprende los coeficientes binomiales, obtenemos $$ c_n = \frac{2}{n} \binom{2n+1}{n-1} - \frac{2}{n-1} \binom{2n-1}{n-2} = C_{n+1} - C_{n} $$

Answer 2

Considerar el espacio de celosía puntos de $(p,q)$ donde $0 \leq p \leq q, q = 0, 1, \dots$; el número de (la más corta) rutas de acceso en este espacio de $(p,q)$ $(0,0)$es el número de boleta $$N(p,q) = \frac{q-p+1}{q+1} \cdot \binom{p+q}{p}; \quad N(0,0) =_D 1.$$ Utilizando esta notación tenemos $ N(n-k,n-1) = \frac{k}{n} \binom{2n-k-1}{n-1} $. El problema pide a mostrar $$\sum_{k=1}^n k N(n-k, n-1) = C_{n+1} - C_{n}.$$

Tenga en cuenta que $ C_{n} $ es la enésima catalán número y que $ C_{n} = N(n,n) $, por lo que $ C_{n+1} - C_{n} $ es el número de rutas de un punto a a $(n-1, n+1)$ $(0,0)$(todos los caminos desde $(n+1, n+1)$ $(0,0)$que no utilizan el punto de $(n,n)$ debe utilizar el punto de $(n-1, n+1)$).

Cualquier ruta de un punto a a $(n-1, n+1)$ a punto de $(0,0)$ debe utilizar uno y sólo uno de los arcos de $a(k)$ que inicie desde el punto de $(k, n)$ y parada en el punto de $(k, n-1)$ donde $0 \leq k \leq n-1$. Pero el número de rutas es $(n-k)N(k,n-1)$ debido a que el número de caminos de $(n-1, n+1)$ a punto de $(k, n)$$(n-k)$, y el número de rutas de un punto a a $(k,n)$ que el uso de arc $a(k)$ es $N(k,n-1)$, por lo que el número total de rutas de un punto a a $(n-1, n+1)$ $(0,0)$es $\sum_{k=0}^{n-1} (n-k) N(k,n-1)$.

Voineasa.