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

Las secuencias en la sugerencia están directamente relacionadas tanto con los caminos de Dyck como con los paréntesis anidados legalmente, los cuales se cuentan mediante números catalanes. Mapear el$+1$términos a los bordes noreste en el camino de Dyck, o para abrir paréntesis; mapear el$-1$términos a los bordes sureste, o para cerrar paréntesis. La condición necesaria en las sucesiones es que las sumas parciales no sean negativas. Esto corresponde a la propiedad de que una ruta de Dyck nunca pasa por debajo de la línea este-oeste, oa la propiedad de que el número acumulativo de paréntesis cerrados nunca excede el número acumulativo de paréntesis abiertos en una expresión correctamente anidada.

Pensando en términos de paréntesis legalmente anidados, podemos asociar, por ejemplo, la expresión (()())() con la matriz

$$\begin{bmatrix}1 & 2 & 4 & 7\\ 3 & 5 & 6 & 8\end{bmatrix}.$$ La primera fila de la matriz contiene las posiciones de los paréntesis abiertos, en orden creciente, y la segunda fila contiene las posiciones de los paréntesis cerrados, en orden creciente. Claramente el$j^\text{th}$el paréntesis de cierre viene después del$j^\text{th}$paréntesis abierto, lo que implica que la matriz tiene todas las propiedades deseadas. Pasar de matrices a expresiones correctamente anidadas es igualmente sencillo.