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

Abstract licence: CC0

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.