Orderings of combinatorial interpretations of Catalan numbers

This article needs more work.

Please help by expanding it!

An ordering of a combinatorial interpretation of Catalan numbers is a method for bijectively mapping the set of structures in some combinatorial interpretation of Catalan numbers to the set of natural numbers via a global ranking function, giving a total ordering for that interpretation.

The OEIS ordering of Catalan structures

The so called OEIS ordering of combinatorial interpretations of Catalan numbers (as currently used in most of the related sequences in OEIS) is based on sequence A014486 (A063171), where each Dyck word has been converted to a binary number (and in case of A014486, converted further into decimal notation) and these numbers are then ordered by their magnitude.

This also conveniently groups each group of $\scriptstyle C_{n}\,$ Dyck words of $\scriptstyle 2n\,$ characters by their size (i.e. all Dyck words of $\scriptstyle 2n\,$ letters come just before those of $\scriptstyle 2n+2\,$ letters), and furthermore, in each subsequence of length $\scriptstyle C_{n}\,$, the Dyck words of the size $\scriptstyle 2n\,$ appear in lexicographic order. (Here $\scriptstyle C_{n}\,$ refers to the $\scriptstyle n\,$th Catalan number, A000108$\scriptstyle (n)\,$.)

Notes

There are also several other, alternative orderings for combinatorial interpretations of Catalan numbers based on various more or less obvious bijections between said combinatorial structures and natural numbers.

Authorship

The first version of this page was written by Antti Karttunen Jul 29-30, 2012.
Copy edited (presentation) by Daniel Forgues Aug 01, 2012.
The whole "Alternative Catalan Orderings" section moved under its own page by Antti Karttunen 12:20, 30 May 2017 (UTC)

Cite this page as

A. Karttunen et al., <a href="http://oeis.org/wiki/Orderings_of_combinatorial_interpretations_of_Catalan_numbers">Orderings of combinatorial interpretations of Catalan numbers</a>, OEIS Wiki.