This site is supported by donations to The OEIS Foundation.

Orderings of combinatorial interpretations of Catalan numbers

From OeisWiki
Jump to: navigation, search


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 Dyck words of characters by their size (i.e. all Dyck words of letters come just before those of letters), and furthermore, in each subsequence of length , the Dyck words of the size appear in lexicographic order. (Here refers to the th Catalan number, A000108.)

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.