A family of words counted by the Catalan numbers

Question

In recent work with Michael Albert and Nik Ruškuc, a family of words has arisen which is counted by the Catalan numbers. I've looked at Richard Stanley's Catalan exercises in EC2 and his Catalan addendum, but I don't see anything that looks to be clearly equivalent, and a bijection to Dyck paths isn't jumping out at me. So I have two questions:

1. Has anyone seen these words, or some equivalent objects, before?

2. Do you see a nice bijection between these words and any family of "classic" Catalan objects such as Dyck paths or noncrossing partitions?

Let $w$ be a word of length $n$ over the natural numbers (including $0$). Then $w$ lies in our family if it satisfies two rules:

1. For all $k\le n-1$, $w_{k+1}\ge w_k-1$.
2. If $w$ contains an $i\ge 1$, then the first $i$ lies between two $i-1$s.

(The word "between" does not imply contiguity, so rule 2 means that when we read $w$ from left to right, we should see an $i-1$ before we see the first $i$, and then at some point after that we should see another $i-1$.)

The number of words of length $n$ that satisfy these conditions is equal to the $n-1$st Catalan number.

For example, the only word of length $2$ that satisfies these rules is $00$, for length $3$ there are two such words, $000$ and $010$, for length $4$ there are five, $$ 0000, 0010, 0100, 0101, 0110, $$ and for length $5$ there are $14$, $$ 00000, 00010, 00100, 00101, 00110, 01000, 01001, $$ $$ 01010, 01011, 01021, 01100, 01101, 01110, 01210. $$

Answer 1

Below my modified answer containing a complete bijection between the above sequences and Dyck paths:

Let $a = (a_1,\ldots,a_n)$ be a sequence of $n$ integers. $a$ satisfies Property $A$ if it satisfies your two conditions above. This is

1. $a_{k+1} \geq a_k−1$,
2. If $a$ contains an $i \geq 1$, then the first $i$ lies between two $i−1$s.

$a$ satisfies Property $B$ if

1. $a_{k+1} \leq a_k+1$,
2. If $a$ contains an $i \geq 1$, then the first $i$ lies between two $i−1$s.

Interchanging neighbours that do not satisfy Property $B1$ does not interfere with Property $A2 = B2$ and should provide a bijection between sequences with Property $A$ and those with Property $B$. E.g. for $n=6$ there are $8$ Property $A$ sequences that do not satisfy Property $B1$: $$001021, 011021, 010021, 010210, 010211, 010212, 012102, 010221.$$ Interchanges $0$'s and $2$'s where necessary gives $$001201, 011201, 012001, 012010, 012011, 012012, 012120, 012201.$$

$a$ satisfies Property $C$ if

1. $a_1 = 0$.
2. $a_{k+1} \leq a_k+1$,
3. If $a$ contains an $i\geq 1$, then there is an $i-1$ after the first $i$,

Properties $B$ and $C$ are equivalent since $B2$ implies that $a_1 = 0$. This then implies that every $i \in a$ has an $i-1$ somewhere to its left, and we can drop this part of condition $B2$ to obtain Property $C3$.

$a$ satisfies Property $D$ if it satisfies $C1$ and $C2$. Sequences with Property $D$ are item $u$ on Stanley's list, and are in natural bijection to Dyck paths (which are here lattice paths from $(0,0)$ to $(n,n)$ that never go below the diagonal $x=y$) by sending a path $D$ to the sequence $a$ where $a_k$ is the number of complete boxes between $D$ and the diagonal at height $i$ (this is a well-known bijection).

Since Property $C$ is strictly stronger than Property $D$, we now have reached an embedding of Sequences of length $n$ with Property $A$ into Dyck paths of length $2n$.

Next, we apply the ''zeta map'' $\zeta$ as defined in Jim Haglund's book on $q,t$-Catalan numbers on page 50. This map is defined by given a sequence $a = (a_1,\ldots,a_n)$ satisfying Property $D$, it returns a Dyck path as follows:

• first, build an intermediate Dyck path (the "bounce path") consisting of $d_1$ north steps, followed by $d_1$ east steps, followed by $d_2$ north steps and $d_2$ east steps, and so on, where $d_i$ is the number of $i-1$'s within $a$. For example, given $a = (0,1,2,2,2,3,1,2)$, we build the path $NE\ NNEE\ NNNNEEEE\ NE$ (this is the dashed path on the right of Figure 3 in the reference).

• Next, the rectangles between two consecutive peaks are filled. Observe that such the rectangle between the $k$th and the $(k+1)$st peak must be filled by $d_k$ east steps and $d_{k+1}$ north steps. In the above example, the rectangle between the second and the third peak must be filled by $2$ east and $4$ north steps, the $2$ being the number of $1$'s in $a$, and $4$ being the number of $2$'s. To fill such a rectangle, scan through the sequence $a$ from left to right, and add east or north steps whenever you see a $k-1$ or $k$, respectively. So to fill the $2 \times 4$ rectangle, we look for $1$'s and $2$'s in the sequence and see $122212$, so this rectangle gets filled with $ENNNEN$.

The complete path we obtain in thus $NENNENNNENEEENEE$. This map sends the dinv statistic (this is, the number of pairs $k<\ell$ with $a_k-a_\ell \in \{0,1\} $) to the area, where the area below the bounce path comes from those pairs with $a_k-a_\ell = 0$, and the parts in between from the pairs with $a_k-a_\ell = 1$). Moreover, an inner touch point is reached if and only if all $i$'s come after all $i-1$'s within $a$ for any $i$. In the example, this happens only for $0$'s and $1$'s, thus giving one touch point.

Given the last observation, we see that $a$ satisfies Property $C3$ if and only if $\zeta(a)$ touches the diagonal only in the very beginning and in the very end, and nowhere in between.

So we thus reached a bijection between sequences satisfying Property $A$ and Dyck paths that do not have inner returns to the diagonal.

Finally, stripping off the first north and the last east step yields a Dyck path of length $2n-2$, and we have obtained a complete bijection.

In order make every step in my bijection visible, I provided a Sage worksheet implementing each step for a better understanding: http://sage.lacim.uqam.ca/home/pub/21/

If anything is unclear or wrong, please let me know so I can try to fix it...

Answer 2

I'm not sure if the following helps, but you can count such sequences by the number of $0$s, $1$s, $2$s, etc. If you have a composition of $n$, $n = c_0 + c_1 + \ldots +c_k$ with $c_i \ge 1$ then the number of such sequences is $$\prod_{i=1}^k \bigg({c_{i} + c_{i-1} - 1\choose c_{i}}- 1\bigg)$$. That is, if you ignore all values which are greater than $i$, the number of ways of placing the $i$s is ${c_{i} + c_{i-1} - 1\choose c_{i}}- 1$. You can place the $i$s in clumps to the left of the non-initial $i-1$s or the end, distributing $c_i$ $i$s into $c_{i-1}$ locations, except that not everything can go at the end.

There is a way to turn such a sequence into a restricted sequence of parentheses so that each $i$ corresponds to a pair of parentheses at level $i$. For each $0$, insert $()$. Then for each $1$ between the $k$th $0$ and the next/end, insert $()$ into the pair corresponding to the $k$th $0$.

For example: $0102210032$. I'll show the parentheses added in each step as square brackets.

$c_0 = 4: [][][][]$

$c_1 = 2 = 1+1+0+0: ([])([])()()$

$c_2 = 3 = 2+1: (([][]))(([]))()()$

$c_3 = 1 = 0+1+0: ((()([])))((()))()()$

This resembles some of the restrictions on Dyck paths of length $n$ counted by $C_{n-1}$ in the Catalan addendum.

Answer 3

This answer summarizes partial progress which was interesting enough to lead to its own question.

Consider sequences which only obey your first condition. Call these $L$-words. ($L$ stands for Lukasiwiecz, because they are more or less the partial sums of the sequences studied by Lukaswiecz.)

There are Catalan many $L$-words. Given an $L$-word, let $p$ be the number of pairs $(i,i+1)$ for which your second rule is violated. So we want to count pairs with $p=0$. Also, let $q+1$ be the number of occurrences of $0$ in the $L$-word. Here is a table: $$\begin{matrix} L-\mbox{word} & p & q \\ 000 & 0 & 2 \\ 010 & 0 & 1 \\ 001 & 1 & 1 \\ 011 & 1 & 0 \\ 012 & 2 & 0 \\ \end{matrix}$$

It appears that the number of $L$-words of length $n$ with given values of $p$ and $q$ only depends on $(p+q, n)$! See my question for more.

Answer 4

This is only a partial answer, and may very well be a dead end, but at least it's long-winded.

First consider only binary words. In this case, condition 1 is vacuous and the only length-$n$ words omitted are of the form $0^a1^{n-a}$ for $a \geq 1$. This leaves $2^n-n$ valid such words.

Here's a simple bijection (probably already written down somewhere) from this set of binary words to Dyck paths of semilength $n$ having at most one long ascent (i.e., at most one maximal sequence of at least two consecutive up steps): Suppose the word $w$ has $1$ at positions $i_1 < i_2 < \cdots < i_k$. Then $w$ maps to a Dyck path that starts with $i_1-1$ copies of $UD$, followed by its long ascent, followed in turn by intermittent $U$s marked by the $i_j$. Specifically, $w$ maps to $$D = (UD)^{i_1-1}U^{n-i_1-k+2}Dv_{i_1+1}v_{i_1+2}\cdots v_{n}$$ where $v_j = UD$ if $j = i_m$ for some $m$ and $v_j = D$ otherwise. The important point here is that the length of the long ascent is determined by the number of $0$s following the initial $1$.

Let's broaden scope a little, but do so from the Dyck path side. Consider Dyck paths for which any long ascent has at most (i.e., exactly) two $U$ steps. These can be mapped to words satisfying conditions 1 and 2 (I think) in an invertible manner. Start scanning the Dyck path from the left, writing down $0$s for each $UD$. At the first ascent (necessarily of the form $UUD$), write a $1$. For each subsequent column, up to the first return to $y=x$ after this point, write down the number of area cells in that column. After that first return, write down the number of area cells plus $1$. For example (placing a period at the first return after the first long ascent), $UDUUDUUDDUDUUDDD.UUDDUDUUDUDD$ maps to $01211210.211221$.

For the general case, some of the long ascents are going to be longer than length $2$. My hope is that one can keep track of how the various long ascents have been lengthened using the values of $w$ corresponding to the additional $D$ steps that must be present to have a Dyck path.