Encontrar el número de caminos monótonos que no cruzan la diagonal

Question

Encontrar el número de caminos monótonos que no cruzan la diagonal

Matemáticas
combinatoria
numeros-catalan

hueco7

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

Entonces, ¿por qué el número de caminos monótonos 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 de hecho la definición del número catalán.

Sin embargo, la relación de recurrencia también da una definición del número catalán: $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$

¿Alguien puede señalar una forma de visualizar intuitivamente la solución para la cantidad de caminos monótonos 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?

Respuestas (1)

Encontrar el número de caminos monótonos que no cruzan la diagonal

julio · Answer 1

Perdón por fotos así pero...

Denotemos a C como el punto donde nuestro buen camino tocó la diagonal la última vez. ingrese la descripción de la imagen aquí

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

ingrese la descripción de la imagen aquí

Existen $P_m$ maneras de ir al grano $C(m,m)$ . Sabemos que para el resto del camino ya no tocaremos la diagonal, lo que significa que nuestro camino se encuentra debajo de la línea DE. Lo que significa que para el resto del camino tenemos $P_{n-(m+1)}$ maneras de hacer eso. Entonces 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$

Vaya, esto es fantástico. Gracias por tomarte la molestia de dibujar los diagramas. Esta es una manera tan ordenada de visualizar el problema.

Encontrar el número de caminos monótonos que no cruzan la diagonal

hueco7

Respuestas (1)

julio

hueco7

Aclaración sobre uno de los problemas de Stanley sobre los números catalanes

Rutas en una cuadrícula que no bajan de 000 ni de lll antes de alcanzar su objetivo.

Una pregunta que pide probar una secuencia igual a números catalanes en la que no puedo pensar

Método rápido para convertir ruta catalana a posición lexicográfica.

Números catalanes usando la recurrencia.

Número de caminos en una grilla con restricciones

Personas sentadas alrededor de dos mesas con sillas numeradas

¿Cuál es el número de números de 4 dígitos no crecientes?

¿Cuál es la probabilidad de que una caminata aleatoria que comienza en 0 llegue a +2 en 2 pasos, 3 pasos, 4 pasos, etc.? [duplicar]

Probabilidad de que dos elementos particulares se agrupen en una partición aleatoria con tamaños fijos