Generalización de los números catalanes: número de formas en que cruzamos la diagonal $k$ veces.

Question

Supongamos que tenemos una cuadrícula cuadrada con n pasos cada una. Uno empieza en la esquina inferior izquierda, toma $2n$ pasos; $n$ de ellos a la derecha y $n$ de ellos hacia arriba y termina en la esquina superior derecha. Si queremos contar el número de caminos que no cruzan la diagonal principal y se quedan en un lado concreto de ella, obtenemos los números catalanes, $C_n=\frac{2n \choose n}{(n+1)}$ . Teniendo en cuenta ambos lados, el total de caminos que no cruzan la diagonal principal se convierte en $2 C_n$ . Una pregunta natural es: ¿cuántos caminos cruzan exactamente la diagonal principal? $k$ ¿tiempos? Llamemos a este número $R_{k,n}$ . Quiero encontrar una expresión de forma cerrada para $R_{k,n}$ . Evidentemente, $R_{0,n}=2C_n$

---

Mi intento y algunas reflexiones

La cuestión aquí: Utilizar los números catalanes proporciona un calentamiento. Tanto @joriki como @robjohn calculan el número de caminos que tienen un segmento positivo (posiblemente vacío) seguido de un segmento negativo (posiblemente vacío). Denotemos esta secuencia, $G_n$ como lo hace joriki. Lo hacen observando que, condicionado a algún punto de corte, simplemente obtenemos dos secuencias catalanas. Por lo tanto, el número de tales trayectorias se convierte en la convolución de los números catalanes consigo mismos. joriki observa que esta secuencia tendrá una función generadora que es el cuadrado de la función generadora de los números catalanes. Utiliza esto para determinar que es simplemente la $n+1$ º número catalán. Otra forma de averiguarlo habría sido utilizar la fórmula general que aparece aquí: Prueba de identidad sobre secuencias binomiales generalizadas. con $k=2$ . Los dos dan la misma respuesta. Esto se puede utilizar para obtener $R_{1,n}$ según la siguiente ecuación (dividimos $R_{1,n}$ por 2 porque la secuencia sólo tiene en cuenta las trayectorias que fueron negativas primero y positivas después, mientras que $R_{1,n}$ incluye las secuencias que fueron positivas en primer lugar):

$$G_n=C_{n+1}=2C_n+\frac{R_{1,n}}{2}$$ $$=> R_{1,n}=2C_{n+1}-4C_n$$

Ahora, ¿podemos aplicar este "truco de convolución" para obtener $R_{k,n}$ ?

Una forma es considerar los caminos que tienen tres secciones. Empiezan con una sección (posiblemente vacía) por debajo de la diagonal principal. Luego, la cruzan y hay una sección (posiblemente vacía) por encima de la diagonal principal. Luego, la cruzan de nuevo y hay una tercera sección (posiblemente vacía) que queda por debajo de la diagonal principal. A diferencia de antes, hay dos puntos de corte y parece que tenemos una convolución triple de los números catalanes consigo mismos. La primera idea es que el número de tales caminos (digamos $H_n$ ) tendrá una función generatriz que es el cubo de la de los números catalanes. Y si seguimos aumentando el número de segmentos, obtendremos potencias cada vez mayores de la función generatriz. Pero esto no puede ser correcto ya que a medida que seguimos aumentando el número de tales segmentos, el número de caminos debería seguir aumentando según la ecuación (5.70) aquí: Prueba de identidad sobre secuencias binomiales generalizadas. . En realidad, llegaremos a un límite superior en algún momento en el que simplemente cubriremos todas las ${2n \choose n}$ caminos. Entonces, ¿cuál es el error en el argumento "convolución de tres vías que lleva a una función generadora que se convierte en el cubo de la función generadora del número catalán"? Una resolución podría ser que el argumento está bien, pero al aumentar los puntos de corte se empiezan a contar doble y triplemente los caminos.

Answer 1

En lugar de permitir posiblemente vacío secciones, dividimos un camino en los puntos de cruce de la diagonal, e ignoramos posibles toque puntos (donde la trayectoria va de arriba/abajo y rebota). Esto da $$R_{0,n}=2C_n,\qquad R_{k,n}=\sum_{m=1}^{n-1}C_m R_{k-1,n-m}\qquad(k,n>0)$$ ( $R_{0,n}$ cuenta "Catalán" $n$ -trayectorias por encima/por debajo de la diagonal (no estrictamente); para obtener una $(k,n)$ -tomamos un $(k-1,n-m)$ -ruta y añadir un "catalán" $m$ -que amplía el último paso). Entonces, en la notación de su pregunta , $$R_{k}(z):=\sum_{n=1}^{\infty}R_{k,n}z^n=2\big(B_2(z)-1\big)^{k+1}=2z^{k+1}B_2(z)^{2k+2}.$$ Utilizar la identidad $(5.70)$ de la pregunta, obtenemos $$R_{k-1}(z)=2z^k\sum_{t=0}^{\infty}\binom{2t+2k}{t}\frac{2k}{2t+2k}z^t\underset{n:=t+k}{\quad=\quad}2\sum_{n=k}^{\infty}\binom{2n}{n-k}\frac{k}{n}z^n,$$ es decir, $R_{k-1,n}=\frac{2k}{n}\binom{2n}{n-k}$ para $1\leqslant k\leqslant n$ .