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.
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityIs 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.
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$.
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.
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.