Por favor ayuda, estoy atascado con este ejemplo. Demostrar que el número catalán es igual al número de caminos de celosía desde a utilizando sólo upsteps y escalones que nunca van por encima del eje horizontal (por lo que hay tantos pasos hacia arriba como pasos hacia abajo). (Estos a veces se denominan rutas de Dyck). Gracias.
Tenga en cuenta que estos caminos son los mismos que los caminos de celosía de a que quedan por debajo de la línea diagonal . Que tales caminos se llamen "buenos caminos" y que los "malos caminos" sean caminos enrejados desde a que cruzan la diagonal. Entonces
# buenos caminos = # caminos - # malos caminos
El número total de caminos de celosía desde a es ya que tenemos que tomar pasos, y tenemos que elegir cuándo tomar la pasos a la derecha.
Para contar el número total de malos caminos, hacemos lo siguiente: cada mal camino cruza la diagonal principal, lo que implica que toca la diagonal justo encima. Específicamente, cada mal camino debe tocar la línea. . Dado un mal camino, divídalo en dos porciones: la porción anterior a la primera vez que toca el camino , y la parte posterior. Si reflejamos la primera porción sobre la línea , entonces tenemos un camino de celosía desde a . Esto da una biyección entre malos caminos y caminos de celosía de a . Puesto que hay tales caminos de celosía, debe haber malos caminos
Juntando todo esto se obtiene
El método típico para contar las rutas de Dyck (que yo sepa) es el siguiente:
Para cada camino de Dyck de a , debe comenzar con un paso hacia arriba y eventualmente regresar al eje x con un paso hacia abajo. Decir es la primera vez vuelve al eje x. Entonces el sub-camino de que va de a es un camino de Dyck (aunque desplazado hacia arriba) de longitud , y la parte de que va de a es también un camino de Dyck (de longitud ).
Cada camino de Dyck admite una única descomposición de esta manera. Es decir, cada camino de Dyck de longitud produce un par ordenado de caminos de Dyck, el primero de longitud y el segundo de longitud . Aquí, puede ser cualquier entero positivo menor o igual que .
Además, cada par ordenado de caminos de Dyck, el primero de longitud y el segundo de longitud da un camino Dyck único bajo esta construcción.
Entonces
pancini
ross milikan