Encontrar el número de trayectorias monótonas que no cruzan la diagonal

Question

Para grandes diagramas relacionados con el número catalán y el número de trayectorias monótonas que no cruzan la diagonal, véase esto: http://en.wikipedia.org/wiki/Catalan_number#Second_proof

Entonces, ¿por qué el número de trayectorias monótonas que no cruzan la diagonal es el número catalán?

Entiendo que a través del "método de reflexión", llegamos a $2n \choose n$ - $2n \choose n-1$ que es efectivamente la definición del número catalán.

Sin embargo, la definición del número catalán también viene dada por la relación de recurrencia: $C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad\text{for }n\ge 0$

¿Puede alguien indicar una forma de visualizar intuitivamente la solución para el número de trayectorias monótonas que no cruzan la diagonal en términos de esta relación de recurrencia en lugar de la fórmula explícita del "método de reflexión" anterior?

Answer 1

Perdón por las fotos así, pero...

Denotemos C como el punto, donde nuestro camino bueno tocó la diagonal la última vez.

Pongamos buenos caminos a los conjuntos según sus puntos $C(m,m)$ . Tenemos $C(0,0),\dots,C(n-1,n-1)$ . ¿Cuántas trayectorias pertenecen al conjunto del punto $C(m,m)$ ?

Hay $P_m$ formas de ir al grano $C(m,m)$ . Sabemos que en el resto de la trayectoria no tocaremos la diagonal, lo que significa que nuestra trayectoria se encuentra bajo la línea DE. Lo que significa que para el resto de la trayectoria tenemos $P_{n-(m+1)}$ formas de hacerlo. Así que el grupo de $C(m,m)$ consiste en $P_m\cdot P_{n-(m+1)}$ buenos caminos. Podemos tomar $m=0,\dots,n-1$ y entonces la suma de todos los caminos posibles es $\sum_{m=0}^{n-1}P_m\cdot P_{n-m-1}=P_n$