Consideremos los paseos sobre una red de números enteros que comienzan en $(0,0)$ donde cada paso es una unidad hacia arriba o hacia la derecha, y que se mantienen en o por encima de la línea $y=2x$ . Cada paso aumenta la cantidad $y-2x$ por $1$ o lo disminuye en $2$ y esta cantidad debe ser siempre no negativa. Según la teorema del voto generalizado el número de estos paseos que terminan en $(a,b)$ es
$$ \frac{b+1-2a}{a+b+1}\binom{a+b+1}{b+1}=\binom{a+b+1}{b+1}-3\binom{a+b}{b+1} $$
Podemos dividir dicho paseo en porciones de la forma $(\to,\to,\dots,\to,\uparrow)$ , que consiste en $k$ pasos a la derecha seguidos de un solo paso hacia arriba. Esta secuencia aumenta la cantidad $y-2x$ por $1-2k$ que puede ser $1,-1,-3,-5,\dots$ etc. Esta es la conexión con su problema; el número de paseos que tienen exactamente $n$ pasos hacia arriba corresponde exactamente a $|B_{n+1}|$ . Para contar los paseos con exactitud $b$ pasos hacia arriba y cualquier número de pasos hacia la derecha, sumamos sobre todos los valores posibles de $a$ en la fórmula anterior. Si $b$ es par, entonces $a$ puede llegar hasta $b/2$ , por lo que el número de paseos es \begin{align} \sum_{a=0}^{b/2}\binom{a+b+1}{b+1}-3\binom{a+b}{b+1} &=\binom{\frac32b+2}{b+2}-3\binom{\frac32b+1}{b+2} =\frac1{b+1}\binom{\frac32b+1}{b} %\\&=\binom{\frac32b+2}{\frac12b}-3\binom{\frac32b+1}{\frac12 b-1} %\\&=\binom{\frac32b+2}{\frac12b}-3\cdot \frac{\frac12b}{\frac32b +2}\binom{\frac32b+2}{\frac12 b} %\\&=\frac{2}{\frac32b+2}\binom{\frac32b+2}{\frac12b} %\\&=\frac{2}{b+2}\binom{\frac32b+1}{\frac12b} \end{align} La primera igualdad se desprende de dos aplicaciones de la identidad del palo de hockey, mientras que la segunda puede verificarse convirtiendo todo en factoriales. Por lo tanto, cuando $n$ es impar, $|B_n|$ es el resultado de la sustitución $n-1$ en la fórmula anterior, por lo que
$$ |B_n|=\frac1n\binom{(3n-1)/2}{n-1}.\tag{$ n\texto{ es impar} $} $$
Puede verificar $|B_1|=\frac11\binom10=1,|B_3|=\frac13\binom42=2,|B_5|=\frac15\binom{7}3=7,$ etc.
Cuando $b$ es impar, el más alto $a$ puede ir es $(b-1)/2$ por lo que en su lugar obtenemos
\begin{align} \sum_{a=0}^{(b-1)/2}\binom{a+b+1}{b+1}-3\binom{a+b}{b+1} =\binom{\frac32b+\frac32}{b+2}-3\binom{\frac32b+\frac12}{b+2}=\frac1{b+2}\binom{\frac32(b+1)}{\frac12(b+1)} \end{align} para que
$$ |B_n|=\frac1{n+1}\binom{\frac32 n}{\frac12 n}.\tag{$ n\texto{ es par} $} $$
También existe una solución de función generadora. Sea $a_n$ sea el número de paseos por la red desde $(0,0)$ a $(n,2n)$ que se mantienen en la línea o por encima de ella $y=2x$ . Con la discusión anterior y un poco de reflexión, $a_n=|B_{2n}|$ . Derivaremos una función generadora para $a_n$ y manejar $|B_{2n+1}|$ por separado más tarde.
Definir el elevación de un punto $(x,y)$ para ser la cantidad $y-2x$ . Nuestros paseos reticulares siempre tienen una elevación no negativa. Un paseo no vacío $W$ puede descomponerse de forma única como una concatenación $$ W=W_1+\uparrow+W_2+\uparrow+W_3+\rightarrow $$ donde
-
$W_1$ es la parte del recorrido hasta la última vez antes de llegar a $(n,2n)$ que el paseo tiene una elevación de $0$ .
-
$W_2$ es la parte del recorrido después de $W_2$ y hasta la última vez tiene una elevación de $1$ .
-
$W_3$ es la parte del recorrido después de $W_3$ y hasta la última vez tiene una elevación de $2$ .
Esto implica que siempre que $n>0$ tenemos que $$ a_n = \sum_{i+j+k=n-1}a_ia_ja_k $$ desde $a_i,a_j,a_k$ representan el número de formas de elegir $W_1,W_2,W_3$ . (Compara y contrasta este análisis con los números catalanes, $C_n$ donde cada camino $C$ puede descomponerse de forma única como $C=C_1+\uparrow+C_2+\to$ que da la recurrencia $C_n=\sum_{i+j=n-1}C_iC_j$ , dando la función generadora de $C_n$ ).
Dejar $A(x)=\sum_{n\ge 0} a_nx^n$ y utilizando el caso base $a_0=0$ esto da la ecuación de la función generadora $$ A(x)=1+xA(x)^3 $$ Esto nos permite resolver $A(x)$ pero es bastante complicado. Afortunadamente, el uso de Inversión de Lagrange puede recuperar $a_n=\frac1{2n+1}\binom{3n}n$ .
Para encontrar $|B_{2n+1}|$ , dejemos que $d_n$ sea el número de paseos desde $(0,0)$ a $(n,2n+1)$ y observe que $d_n=|B_{2n+1}|$ . Considerando la última vez que el paseo tiene una elevación de $0$ se puede deducir que $$ d_n=\sum_{k=0}^n a_ka_{n-k}, $$ para que $D(x)=\sum_{n\ge 0}d_nx^n$ satisface $D(x)=A(x)^2$ . Utilizando nuestra ecuación de la función generadora para $A(x)$ , obtenemos que $$ D(x)^{1/2} = 1+xD(x)^{3/2} $$ A continuación, se puede utilizar la inversión de Lagrange para recuperar $d_n$ . No tengo mucha experiencia con la inversión de Lagrange, así que no estoy seguro de los detalles aquí.
