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) = displaystylesum_{l=1}^{infty}frac{w(n,l)}{(2l-1)!}x^{2l-1}.$$ By the Cauchy product of the Maclaurin series of $ncosh^{n-1}(x)$ and $sinh(x)$ and comparing coefficients of the LHS and RHS, we get the recursion
$$w(n,l)=nsum_{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 $ncdot 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)=nsum_{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

Dave Jung · Answer

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

Answered by Dave Jung on November 3, 2021

Fedor Petrov · Answer

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 quadquad(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 $kin {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.

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

2 Answers

Add your own answers!

Ask a Question