Correlación entre número de caminos y números catalanes.

Permítanme comenzar con su segunda pregunta, ya que esto probablemente será más difícil para Google.

Los números catalanes son bien conocidos por satisfacer la siguiente recurrencia:

$$C_n = \sum_{k=1}^{n} C_{k-1}C_{n-k}$$ Por ejemplo, su primera interpretación de camino de celosía de los números catalanes$C_n$satisface esto condicionando en el primer lugar después del origen que los caminos tocan la diagonal. Tienes que pensar en eso por un minuto, pero el punto es el$k-1$aparece porque para asegurarse de que$k$es la primera vez que golpea la diagonal, tiene que "salir un cuadrado" para los pasos entre el origen y$(k,k)$.

Entonces puedes ver a dónde te lleva ese argumento. Dejar$D_n$sea ​​el número de caminos de celosía que permanecen estrictamente por encima de la diagonal excepto en$(0,0)$y$(n,n)$y exactamente otro punto. Así que si quieres$k$ser la única vez que llegas a la diagonal, entonces tienes que salir un cuadrado a ambos lados de$(k,k)$:

$$D_n=\sum_{k=1}^{n-1} C_{k-1}C_{n-k-1}$$

Al comparar los dos RHS, podemos ver claramente que$D_n=C_{n-1}$.

Cuando entiendes este argumento, es sencillo desenrollarlo en una biyección explícita entre el$D_n$-los caminos de tipo y los caminos catalanes de longitud$2(n-1)$, pero eso te lo dejo a ti :)

---

Su primera pregunta tiene numerosas respuestas, por ejemplo, en la página de Wikipedia .

La recurrencia anterior se puede convertir en la fórmula del producto que menciona; es un ejercicio estándar en la generación de funciones y, de hecho, suele ser la primera solución a una relación de recurrencia no lineal que se resuelve de esta manera. Puede encontrar los detalles en cualquier libro decente sobre combinatoria, o la primera prueba en Wikipedia, o en este sitio web: por ejemplo, Simplificando la relación de recurrencia de números catalanes .

También hay pruebas directas. Todos son al menos un poco complicados, pero puedes tener una idea de lo que implican mirando las otras pruebas de Wikipedia. La forma en que entiendo este truco es que para que la fórmula de su producto sea un número entero, debe ser el caso que$n+1$es un divisor de$\binom{2n+1}{n}$. Esto a su vez puede entenderse como la libertad de una acción de grupo cíclica natural; este y una serie de fenómenos similares / relacionados en la combinatoria algebraica se conocen con el nombre de "The Cycle Lemma".

En cualquier caso, hay muchas maneras en las que creo que los objetos catalanes son más naturalmente cocientes del conjunto de caminos reticulares (apropiados), en lugar de subconjuntos, y por eso veo la rareza en estas pruebas como la misma rareza inherente cada vez que trabajamos con "distinguidos representantes" de las clases de equivalencia, en lugar de las clases mismas.

(En una breve mirada, no pude encontrar pruebas directas en MSE. Seguramente están aquí; los veterinarios no duden en decirnos dónde en los comentarios ^.^)