Paseos cerrados en un $n$ -cubo y permutaciones alternas

Question

Sea $w(n,l)$ denota el número de paseos cerrados de longitud $2l$ desde un vértice determinado del $n$ -cubo. Entonces, es bien sabido que

$$\cosh^n(x)=\sum_{l=0}^{\infty}\frac{w(n,l)}{(2l)!}x^{2l}.$$

Diferenciando ambos lados, obtenemos $$n \cdot \cosh^{n-1}(x)\cdot \sinh(x) = \displaystyle\sum_{l=1}^{\infty}\frac{w(n,l)}{(2l-1)!}x^{2l-1}.$$ Por el producto de Cauchy de la serie de Maclaurin de $n\cosh^{n-1}(x)$ y $\sinh(x)$ y comparando los coeficientes del LHS y RHS, obtenemos la recursión

$$w(n,l)=n\sum_{k=1}^{l}\binom{2l-1}{2k-1}w(n-1,l-k).$$

La recursión anterior tiene la siguiente interpretación combinatoria simple. Contemos el número total de paseos cerrados de longitud $2l$ en el $n$ -cubo. W.L.O.G, que el paso inicial sea a lo largo de la 1ª dimensión. Entonces, de los restantes $2l-1$ pasos, elija $2k-1$ más lugares para avanzar y retroceder la "1ª" dimensión. Tenga en cuenta que hay exactamente una manera para esto una vez que el $2k-1$ se eligen los lugares. Para el resto $2l-2k$ pasos, damos pasos en todas las dimensiones excepto en la 1ª, lo que da como resultado $w(n-1,l-k)$ maneras. Como $k$ es el número de veces que recorremos la 1ª dimensión, sumamos $k$ de 1 a $l$ ( $k>0$ ya que el paso inicial es a lo largo de la 1ª dimensión). Por último, como el paso inicial puede darse en $n$ dimensiones, multiplicamos por $n$ y obtener la recursión anterior.

Mi pregunta es la siguiente Para obtener la recursión anterior, consideramos el producto de Cauchy de la serie de Maclaurin de $n\cdot \cosh^{n-1}(x)$ y $\sinh(x)$ . Esto, sin embargo, es equivalente al producto de Cauchy de la serie de Maclaurin de $n \cdot \cosh^n(x)$ y $\tanh(x),$ que por el mismo método da

$$w(n,l)=n\sum_{k=1}^{l}(-1)^{k+1}\binom{2l-1}{2k-1}A(2k-1)w(n,l-k),$$

en el que los "números tangentes" $A(2k-1)=T_k$ contar el número de permutaciones alternas de $2k-1$ (nótese cómo la dimensión de $w$ no se modifica). Me preguntaba si sería posible una interpretación combinatoria de lo anterior, de forma similar a la primera recursión. El $(-1)^{k+1}$ término insinúa la inclusión-exclusión, pero soy incapaz de dar con una explicación satisfactoria.

El siguiente post sobre $w(n,l)$ se centra en una expresión de forma cerrada, sin mencionar las fórmulas recursivas. Número de paseos cerrados en un $n$ -cubo

Answer 1

Se trata de un tipo de inclusión-exclusión relacionado con la identidad $$ \sum_{k=1}^m (-1)^{k+1} \binom{2m-1}{2k-1}A(2k-1)=1 \quad\quad(1) $$ para todos $m=1,2,\ldots$ .

Para una ruta en el $n$ -cubo con primer paso vertical etiquetamos otro $2k-1$ pasos verticales, tome un peso $(-1)^{k+1}A(2k-1)$ para dicha configuración y resumir. Para $k$ puede elegir $2k-1$ lugares de escalones verticales, después de quitarlos y el primer escalón se obtiene una ruta de longitud $2(l-k)$ . Por tanto, la suma de los pesos de todas las configuraciones es $$\sum_{k=1}^{l}(-1)^{k+1}\binom{2l-1}{2k-1}A(2k-1)w(n,l-k).$$

Por otra parte, la suma de pesos de todas las configuraciones para una ruta fija es igual a 1 debido a (1). De ahí el resultado.

Puedes preguntarte cómo demostrar (1) сombinatorialmente. Esto es probablemente conocido, pero por si acaso aquí está una breve demostración.

Considera tales configuraciones:

(i) $(x_1,\ldots,x_{2m-1})$ es una permutación de $1,\ldots,2m-1$ y $k\in \{1,\ldots,m\}$ ;

(ii) $2k-1$ primeros términos $x_1,\ldots,x_{2k-1}$ están etiquetados y forman una permutación alterna: $x_1<x_2>x_3<\ldots >x_{2k-1}$ ;

(iii) otros términos disminuyen: $x_{2k}>x_{2k+1}>\ldots>x_{2m-1}$ .

Defina el peso de dicha configuración como $(-1)^{k+1}$ . La suma de todos los pesos es el LHS de (1) (empezamos fijando $k$ fijando a continuación el conjunto $\{x_1,\ldots,x_{2k-1}\}$ fijando a continuación una permutación alterna sobre este conjunto). Por otra parte, cualquier permutación excepto $\pi=(2m-1,2m-2,\ldots,1)$ se cuenta dos veces con pesos opuestos, y $\pi$ se cuenta una vez con peso 1.

Answer 2

La ecuación (1) de la respuesta anterior también puede considerarse como el caso en el que $n=1$ para $w(n,l).$ Esto se debe simplemente a que el número de paseos cerrados de longitud $2l$ en un cubo unidimensional es siempre 1 independientemente de $n$ .