# A family of words counted by the Catalan numbers

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

• If you don't make an exception for $i=1$ in rule $3$, you still get Catalan numbers, $C_{n-1}$ instead of $C_n$. So you could say, "the first $i$ is between two $i-1$s." – Douglas Zare May 23 '13 at 12:45
• @Douglas: Thanks for the simplification. I've edited the question accordingly. – Vince Vatter May 23 '13 at 14:03
• Do you happen to have as well the 42 sequences of length 6? – Christian Stump May 23 '13 at 15:14
• Or a little program that generated them? – Christian Stump May 23 '13 at 15:18
• I wonder - mainly since several people seemed to be interested in a solution to this nice question - if it would be appropriate to turn my answer to this question into a short paper. I asked on tea.mathoverflow.net/discussion/1597/… what people in general think about that. I mainly wonder here: what do you (Vince and other participants in this discussion) think about that? I'd be very happy to collaborate with you, in particular if we can as well approach David's nice follow up question at mathoverflow.net/questions/131809. – Christian Stump May 27 '13 at 10:07

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

• Any chance you could link to a more detailed explanation of Haglund's zeta map? His book is online at math.upenn.edu/~jhaglund/books/qtcat.pdf , but I'm not finding it so easy to follow. Thanks! – David E Speyer May 26 '13 at 1:10
• @David: I added the link, thanks! I also added a description of the zeta map (which I actually don't think to be better than the explanation in the book, but maybe it helps anyway). Or did you mean a reference for further background and properties of this map? – Christian Stump May 26 '13 at 9:43
• Thanks Christian! Your description works better than Jim's does for me. – David E Speyer May 28 '13 at 13:53

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.

• Your formula seems to be wrong for $(2,2,1)$. There is only one such sequence: $01210$, but your formula gives $\left( \binom{3}{2}-1 \right) \left( \binom{2}{1} -1 \right) =2$. The basic problem is that, if you make the choice $0101$, there is then no place to put the $2$ obeying the requisite inequalities. – David E Speyer May 23 '13 at 23:32
• @David Speyer: $01021$, no? – Douglas Zare May 24 '13 at 0:12
• Oops, you're right. – David E Speyer May 24 '13 at 1:30

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.

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.