Combinatorics – A Family of Words Counted by the Catalan Numbers

catalan-numbersco.combinatorics

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

Best Answer

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

Related Question