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

Question

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

Answer 1

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_1<x_2>x_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.

Answer 2

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$.