Combinatorial interpretations of Catalan numbers

This article is under construction.

Please do not rely on any information it contains.

This article needs more work.

Please help by expanding it!

A large number of combinatorial interpretations of Catalan numbers are known. Richard Stanley lists 66 different ones in his Enumerative Combinatorics, vol. 2, and several dozens more in his Catalan Addendum. Stanley asks that the reader proves the equicardinality of any two different interpretations $\scriptstyle S_{i}\,$ and $\scriptstyle S_{j}\,$ by exhibiting a simple, elegant bijection $\scriptstyle \phi _{ij}:\,S_{i}\,\rightarrow \,S_{j}\,$ and gives solutions to some of them in his Solutions to Exercises on Catalan and Related Numbers.

Combinatorial interpretations of Catalan numbers

The following table shows the interpretations Dyck paths (Stanley's i), noncrossing handshakes (Stanley's n), plane general trees (Stanley's e), noncrossing circular partitions (Stanley's qq), noncrossing Murasaki diagrams (Stanley's rr), plane binary trees (Stanley's (c) and (d)) as well Eulerian polygon triangulations (Stanley's a) ordered in a way that such natural bijections occur between different interpretations.

For a more complete list (up to size $\scriptstyle n\,$ = 7), and with some additional interpretations (not yet shown here) please see: A014486/a014486.pdf.

The interpretations (i), (n), (e), (qq), (rr), (c/d) and (a) for the sizes 0, 1, 2 and 3 of the Catalan structures.

$\textstyle n\,$ Dyck words (base 10) A014486 Dyck words (base 2) A063171 (i) (n) (e) (qq) (rr) (c/d) (a)

0 0 0 (0 is the empty string) empty Dyck word

1 2 10 ()

2 10 1010 ()() 3 12 1100 (())

4 42 101010 ()()() 5 44 101100 ()(()) 6 50 110010 (())() 7 52 110100 (()()) 8 56 111000 ((()))

Dyck words

Dyck words are words from the Dyck language, which is the language consisting of balanced strings of characters from an alphabet with two characters.

Balanced parenthesizations are obtained by choosing the alphabet to be {(, )}, with characters "(" and ")".

Empty Dyck word

The empty Dyck word (i.e. the empty string) is represented by the number 0 (which is actually a leading 0, used for zero so that it has a visible representation).

Dyck paths (Stanley's i)

(...)

Noncrossing handshakes (Stanley's n)

(...)

Plane general trees (Stanley's e)

(...)

Noncrossing circular partitions (Stanley's qq)

(...)

Noncrossing Murasaki diagrams (Stanley's rr)

(...)

Plane binary trees (Stanley's (c) and (d))

For a natural bijection between plane binary trees and Dyck words & parenthesizations, consider the following situation of "a worm climbing up a binary tree in depth-first, left-to-right fashion" (i.e. preorder traversal), illustration which is adapted from . Here the worm, after having gobbled up all the ones and zeros marking the internal and leaf (respectively) nodes of the binary tree, except the last one, marked as $(0)$, will eventually output a binary string $1101100010$, a member of Totally balanced sequences or Dyck language.

Eulerian polygon triangulations (Stanley's a)

(...)

Automorphisms of combinatorial interpretations of Catalan numbers

Provided that one finds a well-defined bijection between any such interpretation and some of the well-known ones, like parenthesizations or plane binary trees which are encoded by A014486 (either directly, or through a sequence of other such bijections), any rotations, reflections or other symmetry operations of these interpretations can be encoded as integer sequences, as explained in Catalan automorphisms.

Sequences

The empty Dyck word, a very important word of the Dyck language, is included in the following sequences.

Dyck language (set of all Dyck words, the first term being the empty Dyck word) (see A063171$\scriptstyle (n),\,n\,\geq \,0,\,$ comments)

{, (), ()(), (()), ()()(), ()(()), (())(), (()()), ((())), ()()()(), ()()(()), ()(())(), ()(()()), ()((())), (())()(), (())(()), (()())(), (()()()), (()(())), ((()))(), ((())()), ((()())), (((()))), ()()()()(), ()()()(()), ()()(())(), ()()(()()), ()()((())), ()(())()(), ()(())(()), ()(()())(), ()(()()()), ()(()(())), ()((()))(), ()((())()), ()((()())), ()(((()))), (())()()(), (())()(()), (())(())(), (())(()()), (())((())), (()())()(), (()())(()), (()()())(), (()()()()), (()()(())), (()(()))(), (()(())()), (()(()())), (()((()))), ((()))()(), ((()))(()), ((())())(), ((())()()), ((())(())), ((()()))(), ((()())()), ((()()())), ((()(()))), (((())))(), (((()))()), (((())())), (((()()))), ((((())))), ...}

Dyck words interpreted as binary numbers in ascending order. (Where replacing "1" by "(" and "0" by ")" yields well-formed parentheses expressions, see A063171$\scriptstyle (n),\,n\,\geq \,0\,$.)

{0, 10, 1010, 1100, 101010, 101100, 110010, 110100, 111000, 10101010, 10101100, 10110010, 10110100, 10111000, 11001010, 11001100, 11010010, 11010100, 11011000, 11100010, 11100100, 11101000, 11110000, 1010101010, 1010101100, ...}

The binary Dyck words (A063171) in decimal representation. (See A014486$\scriptstyle (n),\,n\,\geq \,0\,$.)

{0, 2, 10, 12, 42, 44, 50, 52, 56, 170, 172, 178, 180, 184, 202, 204, 210, 212, 216, 226, 228, 232, 240, 682, 684, 690, 692, 696, 714, 716, 722, 724, 728, 738, 740, 744, 752, 810, 812, 818, 820, 824, 842, 844, 850, 852, 856, 866, 868, 872, 880, ...}

Catalan numbers: $\scriptstyle C_{n}\,$ gives the count of balanced parenthesizations of $\scriptstyle n,\,n\,\geq \,0,\,$ "(" and $\scriptstyle n,\,n\,\geq \,0,\,$ ")" (represented by "1" and "0" respectively) (Cf. A000108)

{1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, ...} =

{#{ { } }, #{ {10} }, #{ {1010}, {1100} }, #{ {101010}, {101100}, {110010}, {110100}, {111000} }, #{ {10101010}, {10101100}, {10110010}, {10110100}, {10111000}, {11001010}, {11001100}, {11010010}, {11010100}, {11011000}, {11100010}, {11100100}, {11101000}, {11110000} }, ...}

See also

• Catalan numbers
• Orderings of combinatorial interpretations of Catalan numbers