10
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Ira Gessel Jul 18 at 23:34
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.