Número de caminos en una grilla con restricciones

Tenga en cuenta que estos caminos son los mismos que los caminos de celosía de$(0,0)$a$(n,n)$que quedan por debajo de la línea diagonal$\{(x,x) : x \in \mathbb{R} \}$. Que tales caminos se llamen "buenos caminos" y que los "malos caminos" sean caminos enrejados desde$(0,0)$a$(n,n)$que cruzan la diagonal. Entonces

# buenos caminos = # caminos - # malos caminos

El número total de caminos de celosía desde$(0,0)$a$(n,n)$es$\dbinom{2n}{n}$ya que tenemos que tomar$2n$pasos, y tenemos que elegir cuándo tomar la$n$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.$L = \{(x,x+1) : x \in \mathbb{R}\}$. Dado un mal camino, divídalo en dos porciones: la porción anterior a la primera vez que toca el camino$L$, y la parte posterior. Si reflejamos la primera porción sobre la línea$L$, entonces tenemos un camino de celosía desde$(-1,1)$a$(n,n)$. Esto da una biyección entre malos caminos y caminos de celosía de$(-1,1)$a$(n,n)$. Puesto que hay$\dbinom{2n}{n+1}$tales caminos de celosía, debe haber$\dbinom{2n}{n+1}$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$D$de$(0,0)$a$(2n,0)$,$D$debe comenzar con un paso hacia arriba y eventualmente regresar al eje x con un paso hacia abajo. Decir$(2m,0)$es la primera vez$D$vuelve al eje x. Entonces el sub-camino de$D$que va de$(1,1)$a$(2m-1,1)$es un camino de Dyck (aunque desplazado hacia arriba) de longitud$m-1$, y la parte de$D$que va de$(2m,0)$a$(2n,0)$es también un camino de Dyck (de longitud$n-m$).

Cada camino de Dyck admite una única descomposición de esta manera. Es decir, cada camino de Dyck de longitud$n$produce un par ordenado de caminos de Dyck, el primero de longitud$m-1$y el segundo de longitud$n-m$. Aquí,$m$puede ser cualquier entero positivo menor o igual que$n$.

Además, cada par ordenado de caminos de Dyck, el primero de longitud$m-1$y el segundo de longitud$n-m$da un camino Dyck único bajo esta construcción.

Entonces