Dado un número natural $n$ y definir $B_n$ como el conjunto de todas las secuencias $b_1, b_2, \dots, b_n$ de longitud $n$ ...

Question

Dado un número natural $n$ y definir $B_n$ como el conjunto de todas las secuencias $b_1, b_2, \dots, b_n$ de longitud $n$ tal que $b_1 = 1$ y para cada $i = 1, 2, \dots, n-1$ entonces tenemos $$b_{i+1} - b_i \in \{ 1 , -1, -3, -5, -7, \dots \}$$ Dónde $b_i > 0$ para todos $i$ . Encuentre una forma cerrada de $|B_n|$ .

Podemos ver fácilmente (digamos por inducción) que $b_n\leq n$ para todos $n$ .

Así que si decimos $[e_2,e_4,...,e_{2n}]$ son todos los resultados posibles para $b_{2n}$ para ser $2,4,...2n$ y $(o_1,o_3,...,o_{2n-1})$ son todos los resultados posibles para $b_{2n-1}$ para ser $1,3,...,2n-1$ entonces tenemos la siguiente cadena:

$$(1)\to [1]\to (1,1)\to [2,1]\to (3,3,1)\to [7,4,1]\to$$ $$\to (12,12,5,1)\to [30,18,6,1]\to (55,55,25,7,1) \to...$$

así que $|B_n|\in \{1,1,2,3,7,12,30,55,143,...\}$ pero no hay una forma cerrada. ¿Alguna idea de cómo encontrarlo?

Editar: Entonces, el número escrito en un vértice $V$ es un número de caminos (que sólo van hacia arriba o hacia la derecha) desde el vértice rojo hasta el vértice $V$ .

Answer 1

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í.

Answer 2

Bien, aquí está la solución de la función generadora directa, con los detalles de la inversión de Lagrange desarrollados. Necesitamos dos funciones generadoras separadas para los coeficientes pares $|B_{2n}|$ y los coeficientes impar $|B_{2n+1}|$ .

---

Dejemos que $a_n=|B_{2n}|$ con la convención $a_0=1$ . Para cualquier $n\ge 1$ , una secuencia $b$ de longitud $2n$ puede escribirse de forma única como una concatenación $$b = b_1+\color{blue}{(1)}+b_2+\color{red}{(2)}+b_3,$$ donde

• $\color{blue}{(1)}$ es el último $1$ que se produce como una entrada en $b$ .

• $\color{red}{(2)}$ es el último $2$ que se produce como una entrada en $b$ después de la $\color{blue}{(1)}$ .

• $b_1,b_2,b_3$ son las secuencias (posiblemente vacías) que $b$ se divide en borrando $\color{blue}{(1)}$ y $\color{red}{(2)}$ .

Por ejemplo, cuando $b=(\color{blue}1,2,3,2,3,4,5,\color{red}2,3,4)$ entonces $b_1$ está vacía, $b_2=(2,3,2,3,4,5)$ y $b_3=(3,4)$ .

Puede comprobar que $b_1,b_2$ y $b_3$ son todas secuencias de longitud par. Además, al restar $1$ de cada entrada de $b_2$ y $2$ de cada entrada de $b_3$ entonces $b_1,b_2,b_3$ son todas secuencias válidas. Por lo tanto, el número de formas de elegir $b$ es el número de formas de elegir $b_1,b_2,b_3$ dando lugar a la relación recursiva $$a_n = \begin{cases} \displaystyle\sum_{i+j+k=n-1}a_ia_ja_k & n\ge 1\\ 1 & n=0\hspace{2.7cm} \end{cases}$$ Dejar $A(x)=\sum_{n\ge 0}a_nx^n$ Esto implica la ecuación de la función generadora $$A(x)=1+xA(x)^3$$ De este modo, se puede resolver $A(x)$ pero la expresión exacta para $A(x)$ es bastante desordenado, y no se presta fácilmente a una fórmula para $a_n$ . Afortunadamente, podemos utilizar la inversión de Lagrange para recuperar $a_n$ :

Teorema: (Inversión de Lagrange) Sea $f(x)$ y $g(x)$ sean funciones analíticas en cero que son inversas compositivas, es decir $f(g(x))=x$ y para el que $f(0)=g(0)=0$ . Entonces $$[x^k]g(x)^n=\tfrac{n}k [x^{-n}]f(x)^{-k},\tag{$ * $}$$ donde $[x^i]h(x)$ es el coeficiente de $x^i$ en la serie Laurent $h(x)$ .

Para ver cómo nos ayuda esto aquí, dejemos $\def \A {\tilde A}\A(x)=A(x)-1$ para que $${\A(x)}{(1+\A(x))^{-3}}=x$$ Esto significa que $\A(x)$ es la composición inversa de $f(x)=x(1+x)^{-3}$ . Por lo tanto, utilizando $(*)$ con $n=1$ obtenemos que para cualquier $k\ge 1$ , $$\begin{align} |B_{2k}|=a_k=[x^k]\A(x) &=\frac1k[x^{-1}]f^{-k} \\&=\frac1k[x^{-1}]\Big(x(1+x)^{-3}\Big)^{-k} \\&=\frac1k[x^{k-1}](1+x)^{3k} \\&=\frac1k\binom{3k}{k-1},\tag1 \\|B_{2k}|&=\frac1{2k+1}\binom{3k}k \end{align}$$

A continuación, dejemos que $d_n = |B_{2n+1}|$ . Cualquier secuencia $b$ de longitud impar puede descomponerse de forma única como $$b = b_1 + (1) + b_2,$$ donde $b_1$ y $b_2$ son secuencias (posiblemente vacías) de longitud par, y $(1)$ es la última aparición de $1$ como una entrada en $b$ . Por lo tanto, y la secuencia impar es una concatenación de dos secuencias pares. Dejando que $D(x)=\sum_{n\ge 0} d_nx^n$ Esto da lugar a la recursión $d_n=\sum_{i+j=n}a_ia_j$ lo que implica la ecuación de la función generadora $$D(x)=A(x)^2.$$ De nuevo, podemos recuperar $d_k$ mediante la inversión de Lagrange. En primer lugar, recordando $\A(x)=A(x)-1$ , $$D(x) = A(x)^2 = (\A(x)+1)^2=\A(x)^2+2\A(x)+1$$ Ya conocemos los coeficientes de $\A(x)$ sólo necesitamos los coeficientes de $\A(x)^2$ para recuperar los coeficientes $d_k$ de $D(x)$ . Para ello, utilice $(*)$ con $n=2$ : $$\begin{align} [x^k]\A(x)^2=\frac2k[x^{-2}] \Big(x(1+x)^3\Big)^{-k}=\frac2k[x^{k-2}](1+x)^{3k}=\frac2k\binom{3k}{k-2}\tag 2 \end{align}$$ Por último, para $k\ge 1$ , $$\begin{align} |B_{2k+1}|=d_k=[x^k]D(x) &=[x^k]\A(x)^2+2[x^k]\A(x) \\&\stackrel{(1)+(2)}=\frac2k\binom{3k}{k-2}+\frac2k\binom{3k}{k-1} \\&=\frac1{2k+1}\binom{3k+1}{k+1} \end{align}$$