Left factors $L$ of Dyck paths such that $L$ has $n-1$ up steps

Question

From Stanley's Catalan Numbers, problem 28:

Left factors $L$ of Dyck paths such that $L$ has $n-1$ up steps.

I don't understand what this means. If after a sequence of ups, there are equal number or fewer downs, then for $n=4$, I got $13$ paths, not $14$:

uuu/uuud/uuudd/uuuddd
uudu/uudud/uuddu/uuddud
uduu/uduud/uduudd
ududu/ududud

Can anyone explain? Thanks.

Any such left factor with $n-1$ ups and $n-k\le n-1$ downs can be completed to a Dyck path of semilength $n$ by appending $ud^k=ud\dots d$ with $k\ge 1$ downs at the end. This is a bijection, since any Dyck path ends with a well-defined suffix $ud^k$ with $k\ge 1$ downs. — Alexander Burstein, Feb 17 '23 at 08:25
@AlexanderBurstein That is correct. I overinterpreted the $L$ and unfortunately the illustration in the book for $n=3$ does not clarify it. — Haoran Chen, Feb 17 '23 at 08:40

Markus Scheuer · Accepted Answer · 2023-02-17T06:24:31.550

0

We consider the Dyck paths of length $2n$ and take $L$ as a valid left factor if it contains $n-1$ ups. We then have to add the blue left path in the case $n=4$ in the second row and get $C_4=14$ paths. \begin{align*} uudu/uudud/\color{blue}{uududd}/uuddu/uuddud \end{align*}

edited Feb 17 '23 at 06:24

answered Feb 16 '23 at 23:10

Markus Scheuer

108,315

Sorry, my interpretation was, suppose $u_i$ and $d_i$ are the numbers of straight ups and downs respectively, then a path $u_1d_1u_2d_2\cdots$ satisfies $\sum u_i=n-1$ and $d_i\leq u_i$ (I suppose $L$ refers to this, longer l and shorter _?). The path $uududd$ does not satisfy it. – Haoran Chen Feb 17 '23 at 05:09
@HaoranChen: I've added an interpretation. – Markus Scheuer Feb 17 '23 at 05:36
Thank you! I overinterpreted the $L$ and unfortunately the illustration in the book for $n=3$ does not clarify it. – Haoran Chen Feb 17 '23 at 08:43
@HaoranChen: You're welcome! :-) – Markus Scheuer Feb 17 '23 at 09:24

Left factors $L$ of Dyck paths such that $L$ has $n-1$ up steps

1 Answers1