Paseos por el hipercubo: enfoque de la función generadora

Question

El problema es sencillo: dado un hipercubo en $\mathbb{R}^n$ cuyos vértices son $(v_1,..,v_n)$ para cada $v_i$ es igual a 0 ó 1, y hay una arista de u a v si difieren exactamente en un bit, cuenta el número de paseos del vértice u al v en l pasos.

Por lo que sé, hay soluciones utilizando el análisis espectral, pero como estoy interesado en la solución puramente combinatoria, estoy intentando mi enfoque utilizando la función generadora. Pero no tengo suficiente experiencia en la función generadora, así que me gustaría su ayuda sobre cómo proceder.

Sin pérdida de generalidad, supongamos $u = (0, 0, .., 0)$ . Además, podemos suponer que sólo nos interesa el número de bits de v, ya que podemos dividir la respuesta por ${n \choose k}$ después.

Sea $f(r,k)$ es el número de paseos de r pasos que parten de 0 y terminan en un vértice que contiene exactamente k bits 1. Comenzamos con $f(0,0) = 1$ y es fácil obtener la recurrencia

$f(r + 1,k) = n.f(r,k - 1) - (k - 1)f(r,k - 1) + (k + 1)f(r,k + 1)$

Ahora $A_r(x) = \sum_{k = 0}^n f(r,k) x^k$ . No es difícil mostrar la recurrencia

$A_{r + 1}(x) = nxA_r(x) - (x^2 - 1)A'_r(x)$ con $A_0(x) = 1$

¿Alguna ayuda sobre cómo progresar a partir de aquí?

Answer 1

Aquí hay una manera. El número de $l$ -paso a paso de $(0,\cdots,0)$ a $(u_1,\cdots,u_n)$ será

$$[x_1^{u_1}\cdots x_n^{v_n}](x_1+\cdots+x_n)^l \tag{$ \cdot $}$$

donde el polinomio se considera un elemento de $\Bbb Z[x_1,\cdots,x_n]/(x_1^2-1,\cdots,x_n^2-1)$ .

Podemos descomponer $[x_1^{u_1}\cdots,x_n^{u_n}]=[x_1^{u_1}]\cdots[x_n^{u_n}]$ informalmente y considerar cada uno como un mapa de evaluación a través de $[x_i^{0}]P:=P|_{x_i=0}$ y $[x_i^1]:=P|_{x_i=1}-P|_{x_i=0}$ . Si $\vec{u}$ tiene $r$ podemos sin pérdida de generalidad escribirlo como $\vec{u}=(\underbrace{1,\cdots,1}_{r},\underbrace{0,\cdots,0}_{n-r})$ por simetría. Ignore el último $n-r$ ceros.

Ampliar $[x_1^1\cdots x_r^1]$ y solicite $(\cdot)$ para obtener los términos $(\overbrace{1+\cdots+1}^k+\overbrace{0+\cdots+0}^{r-k})^l$ con $\binom{r}{k}$ posibles acuerdos de $0$ s y $1$ s, con el signo $(-1)^{r-k}$ para cada $k=0,\dots,r$ , dando como resultado

$$\#\text{paths}=\sum_{k=0}^r (-1)^{r-k}\binom{r}{k} k^l.$$

Answer 2

Empezaré a escribir mi enfoque. Aún no sé si funcionará o no, pero al menos puedes verlo y tal vez continuarlo.
Existen $n$ dimensiones. Para cada movimiento, elegimos una dirección $1\leq i\leq n$ (norte/sur, este/oeste, arriba/abajo y así sucesivamente para dimensiones superiores) y moverse en esa dirección. En notación vectorial: $a_0=(0,0,\dots,0)$ , $a_{t+1}=a_t+e_i$ donde $a_t\in \mathbb F_2^n$ . Las funciones generadoras exponenciales que vamos a utilizar son: $$ G_i(x)=x^{v_i}(1+\frac 12x^2+\frac1{4!}x^4+\cdots)=x^{v_i}\cosh(x) $$ Así, tenemos una función generadora exponencial para cada dimensión. El coeficiente en la suma es cero cuando la paridad del número de pasos en la dimensión $i$ está mal. Utilizamos funciones generadoras exponenciales, porque el orden en que damos los pasos sí importa, pero todos los pasos en una dirección son idénticos.

Para hallar el número de formas de llegar a $v$ en $r$ pasos, basta con tomar el coeficiente de $x^r$ en $$ \prod_{i=1}^nG_i(x)=x^s\cosh(x)^n $$ donde $s=\sum_{i=1}^nv_i$ es la paridad del número total de pasos que necesitamos. Actualizaré si encuentro una expresión algo agradable para ello o al menos una buena forma de obtenerla.