A Bijection on Dyck Paths and Its Cycle Structure
The known bijections on Dyck paths are either involutions or have
notoriously intractable cycle structure. Here we present a size-preserving
bijection on Dyck paths whose cycle structure is amenable to complete analysis.
In particular, each cycle has length a power of 2.
A new manifestation of the
Catalan numbers as labeled forests crops up en route as does the Pascal matrix mod 2. We use the bijection
to show the equivalence of two known manifestations
of the Motzkin numbers.
Finally, we consider some statistics on the new Catalan manifestation
and the identities they interpret.
