# Walks on hypercube: generating function approach

So the problem is simple: given a hypercube in $\mathbb{R}^n$, whose vertices are $(v_1,..,v_n)$ for each $v_i$ equals 0 or 1, and there is an edge from u to v if they differ at exactly one bit, count the number of walks from vertex u to v in l steps.

As far as I know, there are solutions using spectral analysis, but since I'm interested in purely combinatorial solution, I'm trying my approach using generating function. But I'm not experienced enough in generating function, so I'd like your help on how to proceed.

Without loss of generality, assume $u = (0, 0, .., 0)$. Furthermore, we can assume we are only interested in the number of bits of v, as we can divide the answer by ${n \choose k}$ afterward.

Let $f(r,k)$ be the number of r-step walks starting from 0, ending at a vertex containing exactly k bit 1. We start with $f(0,0) = 1$ and it's easy to obtain the recurrence

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

Now set $A_r(x) = \sum_{k = 0}^n f(r,k) x^k$. It's not hard to show the recurrence

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

Any help on how to progress from here?

• If you're interested in a purely combinatorial solution, a generating function shouldn't qualify in my opinion, since for most things that can be proven using (ugly) generating functions, a nice combinatorical proof using a 'story' and counting the same thing twice is much faster and easier. – Ragnar Feb 13 '14 at 22:04
• Is it allowed to visit the same vertex multiple times? – Ragnar Feb 13 '14 at 22:09
• Yes, as you can see it in the recurrence relation. – Linh Nguyen Feb 13 '14 at 22:11
• Ok. Do you also have a recurrence relation on $k$? – Ragnar Feb 13 '14 at 22:13
• Hmm I have some idea on that, but I can't avoid double counting right now. – Linh Nguyen Feb 13 '14 at 22:28

Here's a way. The number of $l$-step walks from $(0,\cdots,0)$ to $(u_1,\cdots,u_n)$ will be

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

where the polynomial is considered an element of $\Bbb Z[x_1,\cdots,x_n]/(x_1^2-1,\cdots,x_n^2-1)$.

We can decompose $[x_1^{u_1}\cdots,x_n^{u_n}]=[x_1^{u_1}]\cdots[x_n^{u_n}]$ informally and consider each as an evaluation map via $[x_i^{0}]P:=P|_{x_i=0}$ and $[x_i^1]:=P|_{x_i=1}-P|_{x_i=0}$. If $\vec{u}$ has $r$ ones we can without loss of generality write it as $\vec{u}=(\underbrace{1,\cdots,1}_{r},\underbrace{0,\cdots,0}_{n-r})$ because of symmetry. Ignore the last $n-r$ zeros.

Expand $[x_1^1\cdots x_r^1]$ out and apply to $(\cdot)$ to obtain terms $(\overbrace{1+\cdots+1}^k+\overbrace{0+\cdots+0}^{r-k})^l$ with $\binom{r}{k}$ possible arrangements of $0$s and $1$s, with the sign $(-1)^{r-k}$, for each $k=0,\dots,r$, yielding

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

I'll start writing down my approach. I don't know yet whether it will work out or not, but at least you can see it and maybe continue it.
There are $n$ dimensions. For each move, we choose a direction $1\leq i\leq n$ (north/south, east/west, up/down and so on for higher dimensions) and move in that direction. In vector notation: $a_0=(0,0,\dots,0)$, $a_{t+1}=a_t+e_i$, where $a_t\in \mathbb F_2^n$. The exponential generating functions we are going to use are: $$G_i(x)=x^{v_i}(1+\frac 12x^2+\frac1{4!}x^4+\cdots)=x^{v_i}\cosh(x)$$ Thus, we have one exponential generating function for each dimension. The coefficient in the sum is zero when the parity of the number of steps in dimension $i$ is wrong. We use exponential generating functions, because the order in which we take the steps does matter, but all steps in one direction are identical.

To find the number of ways to get to $v$ in $r$ steps, just take the coefficient of $x^r$ in $$\prod_{i=1}^nG_i(x)=x^s\cosh(x)^n$$ where $s=\sum_{i=1}^nv_i$ is the parity of the total number of steps we need. I'll update if I find a somewhat nice expression for it or at least a good way to obtain it.