Return to Answer

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.

Incidentally, if we 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.

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.

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.

Incidentally, if we 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, \textit{Distributions, continued fractions, and the Ehrenfest urn model,} J. Combin. Theory Ser. A 41 (1986), 21–-31.

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.

Incidentally, if we 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.

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.

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.

Incidentally, if we 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, \textit{Distributions, continued fractions, and the Ehrenfest urn model,} J. Combin. Theory Ser. A 41 (1986), 21–-31.