Rutas en una cuadrícula que no bajan de 000 ni de lll antes de alcanzar su objetivo.

El problema se puede resolver de manera similar al problema de la boleta de Bertrand .

Preliminarmente consideramos reflexiones alternativas del punto$(0,0)$en dos lineas$y=x+a$y$y=x+b$. Se puede demostrar fácilmente que el$k$-ésima reflexión tiene las coordenadas:

$$(-1)^k\left(\left\lceil\frac k2\right\rceil a -\left\lfloor\frac k2\right\rfloor b,\left\lfloor\frac k2\right\rfloor b-\left\lceil\frac k2\right\rceil a\right),\tag1$$ si el punto se refleja primero sobre$y=x+a$. Si primero se reflexiona sobre$y=x+b$,$a$y$b$en (1) deben intercambiarse.

Representemos la secuencia de lanzamiento como una trayectoria de celosía en el plano cartesiano de la siguiente manera:

1. Empieza el camino en$(0, 0)$.
2. Cada cabeza es un movimiento a la derecha 1 unidad.
3. Cada cruz es un movimiento hacia arriba 1 unidad.

Nuestro objetivo es dar en el clavo$(p,q)=(t+l,t)$nunca cruzar las líneas$y=x$y$y=x-l$. El número total de caminos es$\binom{2t+l}t$el cual deberá ser disminuido por el número de caminos que crucen al menos una vez las líneas antes mencionadas.

Para calcular el número de caminos 'malos', procedemos de manera muy similar al procedimiento descrito en el enlace que se proporciona al comienzo de la respuesta. El punto final de cada camino que cruza la línea.$y=x$desde abajo se encuentra en la línea$y=x+1$, y el punto final de cada camino que cruza la línea$y=x-l$desde arriba se encuentra en la línea$y=x-l-1$.

Por cada camino 'malo'$P$, definir una nueva ruta$P′$reflejando la parte de$P$hasta el primer punto toca la línea que lo cruza.$P′$es un camino de$(−1, 1)$a$(p, q)$si tocamos la linea$y=x+1$o de$(l+1,-l-1)$a$(p, q)$si tocamos la linea$y=x-l-1$(cf. (1) con$k=1,a=1,b=-l-1$).

Sin embargo, este no es todavía el final de la historia, ya que pueden existir los caminos que cruzan tanto$y=x+1$y$y=x-l-1$. Por el conteo anterior, cada ruta de este tipo se contará como 'mala' dos veces. Por lo tanto, debemos agregar el número de tales rutas, que se pueden calcular de la siguiente manera. asumir un camino$P'$con la parte inicial ya reflejada (sobre la línea de límite que encuentra primero) cruza la otra línea de límite. Definir un nuevo camino$P''$reflejando la parte de$P'$hasta el primer punto toca la segunda línea límite a través de la línea. El punto inicial de todos esos caminos (que cruzan ambas líneas fronterizas en el mismo orden) será el reflejo del punto$(0,0)$primero sobre la primera línea y luego sobre la segunda. Observe que el punto inicial es de nuevo$2t+l$pasos aparte del punto final$(p,q)$. Este proceso de reflexión se puede repetir para los caminos más largos que cruzan repetidamente las líneas límite superior e inferior en orden alterno.

Sustituyendo en (1)$a=1,b=-l-1$se obtiene que el$y$-coordenada de la$k$-ésima reflexión del punto$(0,0)$es

$$\begin{cases} -(-1)^k\left\{k+\left\lfloor\frac k2\right\rfloor l\right\},& \text{if the first reflection is across }y=x+1\\ \hphantom{-}(-1)^{k}\left\{k+\left\lceil\frac k2\right\rceil l\right\},& \text{if the first reflection is across }y=x-l-1 \end{cases}.$$

Con esto a la mano, la expresión final para el número de formas de llegar al punto final sin cruzar las líneas divisorias es:

$$\binom{2t+l}t+\sum_{k\ge1}(-1)^k \left[\binom{2t+l}{t+(-1)^k\left\{k+\left\lfloor\frac k2\right\rfloor l\right\}} +\binom{2t+l}{t-(-1)^k\left\{k+\left\lceil\frac k2\right\rceil l\right\}} \right].$$