A nonempty Dyck path starts with . At its first later return to height zero, cut after the matching . The segment between these two steps stays at height at least one; translating it down one level gives a Dyck path . The remaining suffix is another Dyck path . This gives the unique form .
If the original semilength of a Dyck path is and that of is , then has semilength of a Dyck path . The first return occurs after steps. For the illustrated path UUUDDDUD, , is UUDD, is UD, and the first return occurs after six steps.
Figure 1.
First return decomposes a Dyck path and explains the Catalan recurrence
. Original chosen path of semilength four. Purple steps enclose a blue two-pair path; the orange suffix has one pair. The bar chart independently counts all paths of semilength four by the inside semilength : the four groups have sizes , totaling . The highlighted group contains the displayed path. Details.

Articles by others on the same topic (NaN)

There are currently no matching articles.