This site is supported by donations to The OEIS Foundation.

Combinatorial interpretations of Catalan numbers

From OeisWiki
(Redirected from Plane binary trees)
Jump to: navigation, search


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,[1] and several dozens more in his Catalan Addendum.[2] Stanley asks that the reader proves the equicardinality[3] of any two different interpretations and by exhibiting a simple, elegant bijection and gives solutions to some of them in his Solutions to Exercises on Catalan and Related Numbers.[4]

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.[5]

For a more complete list (up to size = 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.
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

CIC i0.svg CIC n0.svg CIC e0.svg CIC qq0.svg   CIC cd0.svg CIC a0.svg
1 2 10

()

CIC i1.svg CIC n1.svg CIC e1.svg CIC qq1.svg CIC rr1.svg CIC cd1.svg CIC a1.svg
2 10 1010

()()

CIC i2.svg CIC n2.svg CIC e2.svg CIC qq2.svg CIC rr2.svg CIC cd2.svg CIC a2.svg
3 12 1100

(())

CIC i3.svg CIC n3.svg CIC e3.svg CIC qq3.svg CIC rr3.svg CIC cd3.svg CIC a3.svg
4 42 101010

()()()

CIC i4.svg CIC n4.svg CIC e4.svg CIC qq4.svg CIC rr4.svg CIC cd4.svg CIC a4.svg
5 44 101100

()(())

CIC i5.svg CIC n5.svg CIC e5.svg CIC qq5.svg CIC rr5.svg CIC cd5.svg CIC a5.svg
6 50 110010

(())()

CIC i6.svg CIC n6.svg CIC e6.svg CIC qq6.svg CIC rr6.svg CIC cd6.svg CIC a6.svg
7 52 110100

(()())

CIC i7.svg CIC n7.svg CIC e7.svg CIC qq7.svg CIC rr7.svg CIC cd7.svg CIC a7.svg
8 56 111000

((()))

CIC i8.svg CIC n8.svg CIC e8.svg CIC qq8.svg CIC rr8.svg CIC cd8.svg CIC a8.svg

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 [6]. 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 , will eventually output a binary string , a member of Totally balanced sequences or Dyck language.

BintreeWithWormAndGuidelines.svg

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 comments)

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

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

{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.)

{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: gives the count of balanced parenthesizations of "(" and ")" (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

Notes

  1. R. P. Stanley, Exercises on Catalan and Related Numbers, excerpted from Enumerative Combinatorics, vol. 2, version of 23 June 1998.
  2. R. P. Stanley, Catalan Addendum, version of 30 April 2011.
  3. Equality of cardinality is variously called equipotence, equipollence, equinumerosity, or equicardinality.
  4. R. P. Stanley, Solutions to Exercises on Catalan and Related Numbers.
  5. Needs clarification ("combinatorial interpretations of Catalan numbers (...) ordered in a way that such natural bijections occur between different interpretations").
  6. Martin Gardner, Catalan numbers: an integer sequence that materializes in unexpected places, June 1976 Scientific American, p. 122 (Mathematical Games column)