Number of closed walks on an $n$-cube

Question

Is there a known formula for the number of closed walks of length (exactly) $r$ on the $n$-cube? If not, what are the best known upper and lower bounds?

[Edit] Note: the walk can repeat vertices.

Answer 1

Yes (assuming a closed walk can repeat vertices). For any finite graph $G$ with adjacency matrix $A$, the total number of closed walks of length $r$ is given by

$$\text{tr } A^r = \sum_i \lambda_i^r$$

where $\lambda_i$ runs over all the eigenvalues of $A$. So it suffices to compute the eigenvalues of the adjacency matrix of the $n$-cube. But the $n$-cube is just the Cayley graph of $(\mathbb{Z}/2\mathbb{Z})^n$ with the standard generators, and the eigenvalues of a Cayley graph of any finite abelian group can be computed using the discrete Fourier transform (since the characters of the group automatically given eigenvectors of the adjacency matrix). We find that the eigenvalue $n - 2j$ occurs with multiplicity ${n \choose j}$, hence

$$\text{tr } A^r = \sum_{j=0}^n {n \choose j} (n - 2j)^r.$$

For fixed $n$ as $r \to \infty$ the dominant term is given by $n^r + (-n)^r$.

Answer 2

The number of such walks is $2^n$ (the number of vertices of the $n$-cube) times the number of walks that start (and end) at the origin. We may encode such a walk as a word in the letters $1, -1, \dots, n, -n$ where $i$ represents a positive step in the $i$th coordinate direction and $-i$ represents a negative step in the $i$th coordinate direction. The words that encode walks that start and end at the origin are encoded as shuffles of words of the form $i\ -i \ \ i \ -i \ \cdots\ i \ -i$, for $i$ from 1 to $n$. Since for each $i$ there is exactly one word of this form for each even length, the number of shuffles of these words of total length $m$ is the coefficient of $x^m/m!$ in $$\biggl(\sum_{k=0}^\infty \frac{x^{2k}}{(2k)!}\biggr)^{n} = \left(\frac{e^x + e^{-x}}{2}\right)^n. $$ Expanding by the binomial theorem, extracting the coefficient of $x^r/r!$, and multiplying by $2^n$ gives Qiaochu's formula.

Let $W(n,r)$ be the coefficient of $x^r/r!$ in $\cosh^n x$, so that $$W(n,r) = \frac{1}{2^n}\sum_{j=0}^n\binom{n}{j} (n-2j)^r.$$ Then we have the continued fraction, due originally to L. J. Rogers, $$ \sum_{r=0}^\infty W(n,r) x^r = \cfrac{1}{1- \cfrac{1\cdot nx^2}{ 1- \cfrac{2(n-1)x^2}{1- \cfrac{3(n-2)x^2}{\frac{\ddots\strut} {\displaystyle 1-n\cdot 1 x^2} }}}} $$ A combinatorial proof of this formula, using paths that are essentially the same as walks on the $n$-cube, was given by I. P. Goulden and D. M. Jackson, Distributions, continued fractions, and the Ehrenfest urn model, J. Combin. Theory Ser. A 41 (1986), 21–-31.

Incidentally, the formula given above for $W(n,r)$ (equivalent to Qiaochu's formula) is given in Exercise 33b of Chapter 1 of the second edition of Richard Stanley's Enumerative Combinatorics, Volume 1 (not published yet, but available from his web page). Curiously, I had this page sitting on my desk for the past month (because I wanted to look at Exercise 35) but didn't notice until just now that this formula was on it.

Answer 3

Although this is an old question, I wanted to record what I think is a very cute elementary technique for obtaining the summation formula appearing in Qiaochu Yuan's answer. Maybe it is ultimately similar to Ira Gessel's answer: it also uses generating functions, but it avoids use of exponential generating functions.

I saw this technique in this mathstackexchange answer, but have never seen it elsewhere.

Here's the argument.

First of all, we note that it's easy to see, as mentioned in the answer of Derrick Stolee, that the number of closed walks of length $r$ in the $n$-hypercube is $2^n$ times the number of words of length $r$ in the alphabet $[n] := \{1,2,...,n\}$ in which every letter appears an even number of times. So we want to count words of this form.

For a word $w$ in the alphabet $[n]$, let me use $\bf{z}^w$ to denote $\mathbf{z}^w := \prod_{i=1}^{n} z_i^{\textrm{$\#$ $i$'s in $w$}}$, where the $z_i$ are formal parameters. For a set $A \subseteq [n]^{*}$ of such words, I use $F_A(\mathbf{z}) := \sum_{w \in A} \mathbf{z}^{w}$.

For $i=1,\ldots,n$ and ${F}(\mathbf{z})\in\mathbb{Z}[z_1,\ldots,z_n]$ define $$s_i(F(\mathbf{z})) := \frac{1}{2}( F(\mathbf{z}) + F(z_1,z_2,\ldots,z_{i-1},-z_{i},z_{i+1},\ldots,z_n)),$$ a kind of symmetrization operator. We have the following very easy proposition:

Prop. For $A\subseteq [n]^{*}$, $s_i(F_A(\mathbf{z})) = F_{A'}(\mathbf{z})$ where $A' := \{w\in A\colon \textrm{$w$ has an even $\#$ of $i$'s}\}$.

Thus if $A := [n]^r$ is the set of words of length $r$, and $A'\subseteq A$ is the subset of words where each letter appears an even number of times, we get $$ F_{A'}(\mathbf{z}) = s_n(s_{n-1}(\cdots s_1(F_{A}(\mathbf{z})) \cdots ) ) = s_n(s_{n-1}(\cdots s_1((z_1+\cdots+z_n)^r) \cdots ) ) $$ $$= \frac{1}{2^n}\sum_{(a_1,\ldots,a_n)\in\{0,1\}^n}((-1)^{a_1}z_1 + \cdots + (-1)^{a_n}z_n)^r.$$

Setting $z_i := 1$ for all $i$, we see that $$\#A'=\frac{1}{2^n}\sum_{j=0}^{n}\binom{n}{j}(n-2j)^r,$$ and hence that the number of closed walks we wanted to count is $$\sum_{j=0}^{n}\binom{n}{j}(n-2j)^r,$$ as we saw in Qiaochu's answer.

Incidentally, this gives a combinatorial way to compute the eigenvalues of the adjacency matrix of the $n$-hypercube (see Stanley's "Enumerative Combinatorics" Vol. 1, 2nd Edition, Chapter 4 Exercise 68).

Answer 4

Assuming a "closed walk" can repeat vertices, we can count closed walks starting at $0$ by counting the $r$-sequences of $[n]$ so that each number appears an even number of times. The bijection is given by labeling edges by the coordinate that is toggled between the vertices. You can probably count these sequences by inclusion/exclusion and then multiply by $2^n/r$ to account for the choice of start position.