¿Cuántas rutas desde $(0,0)$ a $(2n,2n)$ evitando $(2k+1,2k+1)$ ?

Question

Imagina una red bidimensional que todos $(2k+1, 2k+1)$ están prohibidas. Supongamos que el origen $(0,0)$ está en la esquina inferior izquierda y el punto $(2n,2n)$ es la esquina superior derecha. Un camino en la cuadrícula consiste en una serie de movimientos en los que cada movimiento es una unidad a la derecha o una unidad arriba. Los movimientos diagonales no están permitidos. ¿Cuántas maneras different hay de construir un camino que empiece en $(0,0)$ y terminando en $(2n,2n)$ evitando todos los puntos prohibidos $(2k+1, 2k+1)$ ?

Estoy un poco atascado en esto. Parece que puede ser contado por un montón de cálculos inclusivos-exclusivos, pero ¿hay un resultado más simple?

Answer 1

Sí, hay una buena manera de hacerlo. Esto parece largo, pero es porque lo declaré todo rigurosamente. Si haces dibujos mientras lees esto, tendrá MUCHO más sentido.

Deje que $f(2n)$ denotan el número de caminos de $(0, 0)$ a $(2n, 2n)$ no cruzando a través de un punto de la forma $(2k+1, 2k+1)$ . Afirmo que $f(2n) = C_{2n}$ donde $C_{2n}$ es el $2n$ -el número catalán.

Una conocida propiedad de número catalán $C_{n}$ es que satisface la siguiente fórmula de recursividad: $$ C_{n+1} = \sum_ {i=0}^{n} C_i C_{n-i} \tag {1}$$ Otra propiedad bien conocida es que cuenta el número de caminos desde $(0,0)$ a $(2n,2n)$ que nunca van por encima de la línea $y=x$ .

Probaré el resultado por inducción. Fíjese que es cierto para un caso básico de $n = 0$ . Ahora, supongamos que el resultado es cierto para $f(0), f(2), \dots , f(2n-2)$ .

Para contar $f(2n)$ hacemos el trabajo de casos en el primer punto de la forma $(2k, 2k)$ nuestro camino pasa por (aparte de $(0, 0)$ ). Este trabajo de caso cubre todos los caminos ya que todos los caminos terminan en $(2n, 2n)$ . Supongamos que el primero de estos puntos es $(2k, 2k)$ . WLOG en nuestro primer paso, fuimos $(0, 0) \to (1, 0)$ multiplicaremos por $2$ en nuestro recuento final. Entonces también debemos terminar con $(2k, 2k-1) \to (2k, 2k)$ . Queda por contar el número de caminos que van desde $(1, 0)$ a $(2k, 2k-1)$ sin pasar por ningún punto de la forma $(2k, 2k)$ . Esto es sólo $C_{2k-1}$ ! Después de esto, hay $f(2n-2k)$ formas de terminar el camino $(2k, 2k) \to (2n, 2n)$ . Por lo tanto, tenemos $$f(2n) = \sum_ {k=1}^{n} 2 \cdot C_{2k-1} f(2n-2k)$$ Por la hipótesis inductiva, $f(2n-2k) = C_{2n-2k}$ así que realmente tenemos $$f(2n) = \sum_ {k=1}^{n} 2 \cdot C_{2k-1} C_{2n-2k} = \sum_ {k=1}^n C_{2k-1}C_{2n-2k} + \sum_ {k=1}^nC_{2k-1}C_{2n-2k}$$ usando $j = n-k$ como el iterador para la segunda suma, obtenemos $$f(2n) = \sum_ {k=1}^n C_{2k-1}C_{2n-2k} + \sum_ {j = 0}^{n-1} C_{2j} C_{2n-2j}$$ ¡El final está a la vista! La primera suma es sólo $C_1C_{2n-2}+C_3C_{2n-4} + \dots C_{2n-1}C_{0}$ (es decir, los términos impar de $(1)$ ) mientras que la segunda suma es sólo $C_{0}C_{2n-1} + \dots C_{2n-2}C_1$ (es decir, los términos pares de $(1)$ ). Por lo tanto, deducimos que $f(2n) = C_{2n}$ como se desea.

Estoy seguro de que la prueba bijectiva existe, pero todavía tengo que tratar de encontrarla. Pero dado esto, tal vez usted sea capaz de hacerlo :)