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

69 Views Asked by At

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.

1

There are 1 best solutions below

4
On BEST ANSWER

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*}