This site is supported by donations to The OEIS Foundation.
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,[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]
Contents
- 1 Combinatorial interpretations of Catalan numbers
- 1.1 Dyck words
- 1.2 Dyck paths (Stanley's i)
- 1.3 Noncrossing handshakes (Stanley's n)
- 1.4 Plane general trees (Stanley's e)
- 1.5 Noncrossing circular partitions (Stanley's qq)
- 1.6 Noncrossing Murasaki diagrams (Stanley's rr)
- 1.7 Plane binary trees (Stanley's (c) and (d))
- 1.8 Eulerian polygon triangulations (Stanley's a)
- 2 Automorphisms of combinatorial interpretations of Catalan numbers
- 3 Sequences
- 4 See also
- 5 Notes
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.
| ||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||
|
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.
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
- ↑ R. P. Stanley, Exercises on Catalan and Related Numbers, excerpted from Enumerative Combinatorics, vol. 2, version of 23 June 1998.
- ↑ R. P. Stanley, Catalan Addendum, version of 30 April 2011.
- ↑ Equality of cardinality is variously called equipotence, equipollence, equinumerosity, or equicardinality.
- ↑ R. P. Stanley, Solutions to Exercises on Catalan and Related Numbers.
- ↑ Needs clarification ("combinatorial interpretations of Catalan numbers (...) ordered in a way that such natural bijections occur between different interpretations").
- ↑ Martin Gardner, Catalan numbers: an integer sequence that materializes in unexpected places, June 1976 Scientific American, p. 122 (Mathematical Games column)