Catalan Sequence on a Circle

196 Views Asked by At

A Catalan sequence of length $2n$ is a sequence of $1$'s and $0$'s such that no initial segment of the sequence has more $0$'s than $1$'s.

The number of such sequences is given by the Catalan number $$C_n = \frac{1}{n+1}\binom{2n}{n}.$$ Now, consider the similar definition, a Catalan cycle of length $2n$, being a sequence of $1$'s and $0$'s such that there exists a cyclic permutation of the sequence which results in a Catalan sequence.

For example: $011100$ is a Catalan cycle, since shifting it to the left once results in $111000$ which is a Catalan sequence.

Question: Is every balanced sequence, having exactly $n$ $1$'s and $n$ $0$'s a Catalan cycle? If not, is there a closed expression for the number of Catalan cycles of length $n$?

1

There are 1 best solutions below

0
On BEST ANSWER

Let the cycle be $a(n)$, so $a(n+N)=a(n)$. Let $b(n)$ be the periodic sequence defined by $$b(0)=0,b(n+1)=b(n)+2a(n)-1$$ In other words, you go up when $a(n)=1$ and go down when $a(n)=0$.
$b(n)$ is periodic because $a(n)$ is balanced.
Start at the lowest point of $b(n)$. The sequence of $a(n)$ that follow will be a Catalan sequence.