Recent and Noteworthy Sequences in the OEIS ®

NEW

Problem: For integers $m\ge1,\ n\ge0,\ 0\le k\le n$, let $T(m,n,k)$ count words $S=s_1\cdots s_{m(n+1)}$ over $\{L,R\}$, starting with $L$, with $m(k+1)$ letters $L$ and $m(n-k)$ letters $R$, whose direction sequence modulo $m$ is equidistributed as in OEIS A197654. The conjectured recurrence is

with $T(m,n,n)=1$ and $T(1,n,k)=\binom nk$.

Result: The recurrence is true. More generally,

with the convention $\binom n{n+1}=0$. This gives the OEIS formula for $m=5$.

Proof sketch. Let $p=k+1$, $q=n-k$. A word defines a closed walk on the cycle graph with vertices $\mathbb Z/m\mathbb Z$: $L$ crosses the next edge positively, $R$ crosses it negatively. The OEIS direction attached to a letter is exactly the edge of this cycle crossed by that step. Hence the meander condition says that each of the $m$ cycle-edges is crossed exactly $n+1=p+q$ times.

In any closed walk, flow conservation at every vertex implies that the number of positive crossings of each edge is constant. Since the total number of positive crossings is $mp$, each edge is crossed positively $p$ times and negatively $q$ times. Thus $T(m,n,k)$ is the number of unlabeled Eulerian circuits, starting with a fixed positive edge, in the directed multigraph on the $m$-cycle having $p$ parallel positive arcs and $q$ parallel negative arcs on every edge.

For $m\ge2$, label all parallel arcs. By the BEST theorem, the number of labeled Eulerian circuits starting with a fixed positive arc is

where $\tau_0$ is the number of in-arborescences rooted at the initial vertex. Such an arborescence is obtained by choosing, for some $j=0,\dots,m-1$, $j$ consecutive negative arcs toward the root and $m-1-j$ positive arcs toward the root, so

Passing from labeled to unlabeled circuits divides by

Therefore

Since

this simplifies to

The case $m=1$ is immediate: every word is a meander, and the count is $\binom nk$.

For $k<n$, putting $a=\binom nk$, $b=\binom n{k+1}=\binom n{n-1-k}$,

which is exactly the conjectured recurrence. For $k=n$, $q=0$, so the only word is $L^{m(n+1)}$, hence $T(m,n,n)=1$.

Citation: Uses the BEST theorem: de Bruijn, van Aardenne-Ehrenfest, Smith, and Tutte, “On the number of Euler circuits in a graph,” Indagationes Mathematicae 13 (1951), 383–388. Source statement: OEIS A197654.