Una partición intuitivo de los números de catalán

Question

El enésimo catalán número, $C(n)$ cuenta el número de cadenas binarias con n $0$'s y n $1$'s tales que cualquier subcadena inicial tiene al menos tantos $0$'s $1$'s.

Sé que la fórmula para el n-ésimo catalán número es $C(n)=\frac{1}{n+1}\binom{2n}{n}$ y la fórmula para el número de cadenas binarias con n $0$'s y n $1$s'es sólo $B(n)=\binom{2n}{n}$

Es allí una manera natural para particionar el conjunto de todas las cadenas binarias con n $0$'s y n $1$'s en grupos de tamaño $n+1$ de manera tal que cada partición contiene exactamente una cadena con la propiedad de que cualquier subcadena inicial contiene al menos tantos $0$'s $1$'s?

Answer 1

La respuesta es sí; está implícito en esta prueba que $C_n=\frac1{n+1}\binom{2n}n$. En la terminología, comience con cualquier ruta cuya superación es $0$ y revertir el algoritmo para producir en caminos de la sucesión con excedencia $k$ $k=1,\dots,n$.

Answer 2

He robado la siguiente cita de Cuatro Pruebas de la Boleta Teorema de Marc Renault en Matemáticas de la Revista, Volumen 80, Nº 5, diciembre de 2007. Todo el artículo se hace muy interesante de leer.

Considere la posibilidad de la ${2n\choose n}$ posible entramado de rutas partiendo del origen y consta de $n$ upsteps $(1,1)$ $n$ downsteps $(1,-1)$. Resulta que, sorprendentemente, que el número de estos caminos con $i$ upsteps por encima de la $x$-eje $(0\leq i\leq n)$ es el mismo, independientemente del valor de $i$. En consecuencia, el número de rutas con todos los $n$ upsteps por encima de la $x$-eje debe ser ${2n\choose n}/(n+1)$.