Home > Catalan number
The Catalan numbers, named after the Belgian mathematician Eugène Charles Catalan (1814—1894), form a sequence of natural numbers that occur in various counting problems in combinatorics. The nth Catalan number is defined by-
(see binomial coefficient). The first Catalan numbers (sequence A000108 in OEIS) for n = 0, 1, 2, 3, ... are
- 1, 1, 2, 5, 14, 42, 132, 429, 1430,...
All Catalan numbers are natural numbers because one can verify that
-
1 Applications in combinatorics
- Cn is the number of Dyck words of length 2n. A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's. For example, the following are the Dyck words of length 6: XXXYYY, XYXXYY, XYXYXY, XXYYXY, XXYXYY. Accordingly, C3 = 5. Thinking of X as an open parenthesis and of Y as a closed one, every Dyck word of length 2n can be seen as an expression with n pairs of parentheses correctly placed together: ((())), ()(()), ()()(), (())(), (()()). Dyck words can be naturally represented as certain paths in a grid with n+1 by n+1 vertices connected by vertical and horizontal lines. The paths start in the lower left corner, end in the upper right corner, always move up or right, and never pass above the diagonal. X stands for "move right" and Y stands for "move up".
- One can count Dyck words with the following trick due to D. André: focus on those words containing n X's and n Y's that are not Dyck words. In such a word, find the first Y that violates the Dyck condition, and then flip all letters following this Y from Y to X and vice versa. You obtain a word with n + 1 Y's and n − 1 X's, and in fact every word with n + 1 Y's and n − 1 X's can be obtained in this fashion in precisely one way. The number of these words is equal to
-
- which is therefore the same as the number of non-Dyck words; the number of Dyck words must then be
-
- which is the nth Catalan number Cn.
- Cn is the number of different ways n + 1 factors can be completely parenthesized. For n=3 for example, we have the following 5 different parenthesizations of 4 factors: a(b(cd)), a((bc)d), (ab)(cd), (a(bc))d, ((ab)c)d. Such expressions can be naturally represented as rooted ordered binary treeGraph theory Trees (structure) In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. A forest is a graph in which any two vertices are connected by at most one path. An equivalent definition is that a forest is as, so Cn also counts the number of these trees with n + 1 leaves.
- Cn is the number of different ways a polygonA polygon (from the Greek poly for "many", and gonos for "angle") is a closed planar path composed of a finite number of sequential straight line segments. The straight line segments that make up the polygon are called its sides or edges and the points wh with n + 2 sides can be cut into triangles by connecting vertices with straight lines.
- If w is a finite sequence of different integers, we define a reordering S(w) of w recursively as follows: write w = unv where n is the largest element in w and u and v are shorter sequences, and set S(w) = S(u)S(v)n, with S being the identity for one-element sequences. A permutationThis article is about permutation a mathematical concept. See permutation (music) for the application of this concept to music. In mathematics, the concept of a permutation expresses the idea that objects that can be distinguished may be arranged in vario w of {1, ..., n} is called stack-sortable if S(w) = (1, ..., n). The number of stack-sortable permutations of {1, ..., n} is equal to Cn.
- Cn is the number of noncrossing partitionIn combinatorial mathematics, the topic of noncrossing partitions has assumed some importance because of (among other things) its application to the theory free probability. Definition A partition of a set S is a pairwise disjoint set of non-empty subsetss of the set { 1, ..., n }. A fortiori, Cn never exceeds the nth Bell numberThe Bell numbers named in honor of Eric Temple Bell, are a sequence of integers arising in combinatorics that begins thus (sequence in OEIS): : In general, B is the number of partitions of a set of size n''. B is 1 because there is exactly one partition o. Cn is also the number of noncrossing partitions of the set { 1, ..., 2n } in which every block is of size 2. The conjunction of these two facts may be used in a proof by mathematical inductionMathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers, or otherwise is true of all members of an infinite sequence. A somewhat more general form of argument used in mathe that all of the free cumulants of degree more than 2 of the Wigner semicircle law are zero.
- Cn is the number of non-isomorphic full binary trees with n vertices that have children, usually called internal vertices or branches. (A rooted binary tree is full if every vertex has either two children or no children.)
