# Closed walks on an $n$-cube and alternating permutations

Let $$w(n,l)$$ denote the number of closed walks of length $$2l$$ from a given vertex of the $$n$$-cube. Then, it is well-known that

$$\cosh^n(x)=\sum_{l=0}^{\infty}\frac{w(n,l)}{(2l)!}x^{2l}.$$

Differentiating both sides, we get $$n \cdot \cosh^{n-1}(x)\cdot \sinh(x) = \displaystyle\sum_{l=1}^{\infty}\frac{w(n,l)}{(2l-1)!}x^{2l-1}.$$ By the Cauchy product of the Maclaurin series of $$n\cosh^{n-1}(x)$$ and $$\sinh(x)$$ and comparing coefficients of the LHS and RHS, we get the recursion

$$w(n,l)=n\sum_{k=1}^{l}\binom{2l-1}{2k-1}w(n-1,l-k).$$

The above recursion has the following simple combinatorial interpretation. Let us count the total number of closed walks of length $$2l$$ on the $$n$$-cube. W.L.O.G, let the initial step be along the 1st dimension. Then, out of the remaining $$2l-1$$ steps, choose $$2k-1$$ more places to step back and forth the "1st" dimension. Note that there is exactly one way for this once the $$2k-1$$ places are chosen. For the remaining $$2l-2k$$ steps, we take steps in every dimension except the 1st, resulting in $$w(n-1,l-k)$$ ways. As $$k$$ is the number of times we walk back and forth the 1st dimension, we sum $$k$$ from 1 to $$l$$ ($$k>0$$ as the initial step is along the 1st dimension). Finally, as the initial step can be taken in $$n$$ dimensions, we multiply by $$n$$ and get the above recursion.

My question is the following. To obtain the above recursion, we considered the Cauchy product of the Maclaurin series of $$n\cdot \cosh^{n-1}(x)$$ and $$\sinh(x)$$. This, however, is equivalent to the Cauchy product of the Maclaurin series of $$n \cdot \cosh^n(x)$$ and $$\tanh(x),$$ which by the same method gives

$$w(n,l)=n\sum_{k=1}^{l}(-1)^{k+1}\binom{2l-1}{2k-1}A(2k-1)w(n,l-k),$$

in which the "tangent numbers" $$A(2k-1)=T_k$$ count the number of alternating permutations of $$2k-1$$ elements (note how the dimension of $$w$$ is unchanged). I was wondering if a combinatorial interpretation of the above was possible, in a similar fashion to the first recursion. The $$(-1)^{k+1}$$ term hints inclusion-exclusion, but I'm unable to come up with a satisfactory explanation.

The following post on $$w(n,l)$$ focuses on a closed-form expression, without mention of recursive formulae. Number of closed walks on an $n$-cube

This is a kind of inclusion-exclusion related to the identity $$\sum_{k=1}^m (-1)^{k+1} \binom{2m-1}{2k-1}A(2k-1)=1 \quad\quad(1)$$ for all $$m=1,2,\ldots$$.

For a route on the $$n$$-cube with first step being vertical we label other $$2k-1$$ vertical steps, take a weight $$(-1)^{k+1}A(2k-1)$$ for such a configuration and sum up. For given $$k$$, you may choose $$2k-1$$ places of vertical steps, after removing them and the first step you get a route of length $$2(l-k)$$. So the sum of weights of all configurations is $$\sum_{k=1}^{l}(-1)^{k+1}\binom{2l-1}{2k-1}A(2k-1)w(n,l-k).$$

On the other hand, the sum of weights of all configurations for a fixed route equals 1 due to (1). Thus the result.

You may ask how to prove (1) сombinatorially. This is most probably known, but for any sake here is a short proof.

Consider such configurations:

(i) $$(x_1,\ldots,x_{2m-1})$$ is a permutation of $$1,\ldots,2m-1$$ and $$k\in \{1,\ldots,m\}$$;

(ii) $$2k-1$$ first terms $$x_1,\ldots,x_{2k-1}$$ are labelled and form an alternating permutation: $$x_1x_3<\ldots >x_{2k-1}$$;

(iii) other terms are decreasing: $$x_{2k}>x_{2k+1}>\ldots>x_{2m-1}$$.

Define the weight of such configuration as $$(-1)^{k+1}$$. The sum of all weights is LHS of (1) (we start with fixing $$k$$, next fixing the set $$\{x_1,\ldots,x_{2k-1}\}$$, next fix an alternating permutation on this set). On the other hand, any permutation except $$\pi=(2m-1,2m-2,\ldots,1)$$ is counted twice with opposite weights, and $$\pi$$ is counted once with weight 1.

• Fedor's proof of (1) can be found in my paper with Richard Stanley, Algebraic enumeration, Handbook of Combinatorics, Vol. 2, pp. 1021–1061, Elsevier Sci. B. V., Amsterdam, 1995. dedekind.mit.edu/~rstan/pubs/pubfiles/79.pdf and in Anthony Mendes, A note on alternating permutations, Amer. Math. Monthly 114 (2007), no. 5, 437–440. jstor.org/stable/27642223. Jul 18 '20 at 23:34

Equation (1) from the above answer can also be viewed as the case in which $$n=1$$ for $$w(n,l).$$ This is simply because the number of closed walks of length $$2l$$ on a one-dimensional cube is always 1 regardless of $$n$$.