|
In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named for the Belgian mathematician Eugène Charles Catalan (1814–1894). Combinatorics is a branch of mathematics that studies finite collections of objects that satisfy specified criteria, and is in particular concerned with counting the objects in those collections (enumerative combinatorics) and with deciding whether certain optimal objects exist (extremal combinatorics). ...
In mathematics, a sequence is a list of objects (or events) arranged in a linear fashion, such that the order of the members is well defined and significant. ...
In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ...
See: Enumeration Combinatorial enumeration Counting problem (computability theory) This is a disambiguation page: a list of articles associated with the same title. ...
A visual form of recursion known as the Droste effect. ...
Leonhard Euler, one of the greatest mathematicians of all time A mathematician is a person whose primary area of study and research is the field of mathematics. ...
Eugène Charles Catalan Eugène Charles Catalan (May 30, 1814 - February 14, 1894) was a Belgian mathematician. ...
The nth Catalan number is given directly in terms of binomial coefficients by In mathematics, particularly in combinatorics, the binomial coefficient of the natural number n and the integer k is the number of combinations that exist. ...
The first Catalan numbers (sequence A000108 in OEIS) for n = 0, 1, 2, 3, … are The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ...
- 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …
Look up one in Wiktionary, the free dictionary. ...
Look up one in Wiktionary, the free dictionary. ...
“II†redirects here. ...
Look up five in Wiktionary, the free dictionary. ...
14 (fourteen) is the natural number following 13 and preceding 15. ...
Look up forty-two in Wiktionary, the free dictionary. ...
132 is the natural number following 131 and preceding 133. ...
Properties
An alternative expression for Cn is This shows that Cn is a natural number, which is not a priori obvious from the first formula given. This expression forms the basis for André's proof of the correctness of the formula (see below under second proof). In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ...
The Catalan numbers satisfy the recurrence relation In mathematics, a recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms. ...
They also satisfy: which can be a more efficient way to calculate them.
Asymptotically, the Catalan numbers grow as
in the sense that the quotient of the nth Catalan number and the expression on the right tends towards 1 for n → ∞. (This can be proved by using Stirling's approximation for n!.) Wikibooks Calculus has a page on the topic of Limits In mathematics, the concept of a limit is used to describe the behavior of a function as its argument either gets close to some point, or as it becomes arbitrarily large; or the behavior of a sequences elements, as...
The relative difference between (ln x!) and (x ln x - x) approaches zero as x increases. ...
The only Catalan numbers Cn which are odd are those for which n = 2k − 1. All others are even.
Proof of the formula There are several ways of explaining why the formula solves the combinatorial problems listed above. The first proof below uses a generating function. The second and third proofs are examples of bijective proofs; they involve literally counting a collection of some kind of object to arrive at the correct formula. In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. ...
Bijective proof In combinatorics, bijective proof, is a proof technique that finds a bijective function between two sets and and thus proves that both sets have the same number of elements: . Example For instance, consider the number of ways in which a committee can be formed from a total of...
First proof We start with the observation that several of the combinatorial problems listed above can easily be seen to satisfy the recurrence relation In mathematics, a recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms. ...
For example, every Dyck word w of length ≥ 2 can be written in a unique way in the form - w = Xw1Yw2
with (possibly empty) Dyck words w1 and w2.
The generating function for the Catalan numbers is defined by In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. ...
As explained in the article titled Cauchy product, the sum on the right side of the above recurrence relation is the coefficient of xn in the product In mathematics, the Cauchy product, named in honor of Augustin Louis Cauchy, of two strictly formal (not necessarily convergent) series usually, of real or complex numbers, is defined by a discrete convolution as follows. ...
Therefore Multiplying both sides by x, we get So we have and hence (the other root of the quadratic equation cannot be expanded as a power series in x, since it has a pole at 0.
The square root term can be expanded as a power series using the identity
which can be proved, for example, by the binomial theorem, (or else directly by considering repeated derivatives of ) together with judicious juggling of factorials. Substituting this into the above expression for c(x) produces, In mathematics, the binomial theorem is an important formula giving the expansion of powers of sums. ...
making the substitution k = n − 1, and going back to the original variable n, Equating coefficients yields the desired formula for Cn.
Second proof This proof depends on a trick known as the reflection principle (not to be confused with the Schwarz reflection principle in complex analysis). The reflection principle has been widely, but incorrectly, attributed to André; it is actually due to Aebly and Mirimanoff. It is most easily expressed in terms of the "monotonic paths which do not cross the diagonal" problem (see above). In mathematics, the Schwarz reflection principle is a way to extend the domain of definition of an analytic function of a complex variable F , which is defined on the upper half-plane and has well-defined and real number boundary values on the real axis. ...
Complex analysis is the branch of mathematics investigating functions of complex numbers, and is of enormous practical use in many branches of mathematics, including applied mathematics. ...
Figure 1. The green portion of the path is being flipped. Suppose we are given a monotonic path in an n × n grid that does cross the diagonal. Find the first edge in the path that lies above the diagonal, and flip the portion of the path occurring after that edge, along a line parallel to the diagonal. (In terms of Dyck words, we are starting with a sequence of n X's and n Y's which is not a Dyck word, and exchanging all X's with Y's after the first Y that violates the Dyck condition.) The resulting path is a monotonic path in an (n − 1) × (n + 1) grid. Figure 1 illustrates this procedure; the green portion of the path is the portion being flipped. Image File history File links illustrating reflection principle in Catalan numbers article File history Legend: (cur) = this is the current file, (del) = delete this old version, (rev) = revert to this old version. ...
Since every monotonic path in the (n − 1) × (n + 1) grid must cross the diagonal at some point, every such path can be obtained in this fashion in precisely one way. The number of these paths is equal to
- .
Therefore, to calculate the number of monotonic n × n paths which do not cross the diagonal, we need to subtract this from the total number of monotonic n × n paths, so we finally obtain which is the nth Catalan number Cn.
Third proof The following bijective proof, while being more involved than the previous one, provides a more natural explanation for the term n + 1 appearing in the denominator of the formula for Cn.
Figure 2. A path with exceedance 5. Suppose we are given a monotonic path, which may happen to cross the diagonal. The exceedance of the path is defined to be the number of pairs of edges which lie above the diagonal. For example, in Figure 2, the edges lying above the diagonal are marked in red, so the exceedance of the path is 5. Image File history File links part of the second proof of the Catalan number formula File history Legend: (cur) = this is the current file, (del) = delete this old version, (rev) = revert to this old version. ...
Now, if we are given a monotonic path whose exceedance is not zero, then we may apply the following algorithm to construct a new path whose exceedance is one less than the one we started with.
- Starting from the bottom left, follow the path until it first travels above the diagonal.
- Continue to follow the path until it touches the diagonal again. Denote by X the first such edge that is reached.
- Swap the portion of the path occurring before X with the portion occurring after X.
The following example should make this clearer. In Figure 3, the black circle indicates the point where the path first crosses the diagonal. The black edge is X, and we swap the red portion with the green portion to make a new path, shown in the second diagram.
Figure 3. The green and red portions are being exchanged. Notice that the exceedance has dropped from three to two. In fact, the algorithm will cause the exceedance to decrease by one, for any path that we feed it. Image File history File links part of the second proof of the Catalan number formula File history Legend: (cur) = this is the current file, (del) = delete this old version, (rev) = revert to this old version. ...
Figure 4. All monotonic paths in a 3×3 grid, illustrating the exceedance-decreasing algorithm. It is also not difficult to see that this process is reversible: given any path P whose exceedance is less than n, there is exactly one path which yields P when the algorithm is applied to it. Image File history File links part of the second proof of the Catalan number formula File history Legend: (cur) = this is the current file, (del) = delete this old version, (rev) = revert to this old version. ...
This implies that the number of paths of exceedance n is equal to the number of paths of exceedance n − 1, which is equal to the number of paths of exceedance n − 2, and so on, down to zero. In other words, we have split up the set of all monotonic paths into n + 1 equally sized classes, corresponding to the possible exceedances between 0 and n. Since there are
monotonic paths, we obtain the desired formula Figure 4 illustrates the situation for n = 3. Each of the 20 possible monotonic paths appears somewhere in the table. The first column shows all paths of exceedance three, which lie entirely above the diagonal. The columns to the right show the result of successive applications of the algorithm, with the exceedance decreasing one unit at a time. Since there are five rows, C3 = 5.
Hankel matrix The n×n Hankel matrix whose (i, j) entry is the Catalan number Ci+j has determinant 1, regardless of the value of n. For example, for n = 4 we have In linear algebra, a Hankel matrix, named after Hermann Hankel, is a square matrix with constant (positive sloping) skew-diagonals, e. ...
In algebra, a determinant is a function depending on n that associates a scalar, det(A), to every n×n square matrix A. The fundamental geometric meaning of a determinant is as the scale factor for volume when A is regarded as a linear transformation. ...
Note that if the entries are "shifted", namely the Catalan numbers Ci+j+1, the determinant is still 1, regardless of the size of n. For example, for n = 4 we have - .
The Catalan numbers form the unique sequence with this property.
Quadruple factorial The quadruple factorial is given by , or . This is the solution to labelled variants of the above combinatorics problems. It is entirely distinct from the multifactorials. For factorial rings in mathematics, see unique factorisation domain. ...
History The Catalan sequence was first described in the 18th century by Leonhard Euler, who was interested in the number of different ways of dividing a polygon into triangles. The sequence is named after Eugène Charles Catalan, who discovered the connection to parenthesized expressions during his exploration of the Towers of Hanoi puzzle. The counting trick for Dyck words was found by D. André in 1887. (17th century - 18th century - 19th century - more centuries) As a means of recording the passage of time, the 18th century refers to the century that lasted from 1701 through 1800. ...
Leonhard Euler (pronounced Oiler; IPA ) (April 15, 1707 – September 18 [O.S. September 7] 1783) was a pioneering Swiss mathematician and physicist, who spent most of his life in Russia and Germany. ...
Eugène Charles Catalan Eugène Charles Catalan (May 30, 1814 - February 14, 1894) was a Belgian mathematician. ...
A model set of the Towers of Hanoi The Tower of Hanoi (also called Towers of Hanoi) is a mathematical game or puzzle. ...
See also In mathematics, in the area of combinatorics, the binomial transform is a transformation of sequence by computing its forward differences. ...
This is a list of factorial and binomial topics, by Wikipedia page. ...
In combinatorics, Bertrands ballot theorem is the solution to the question: In an election where one candidate receives p votes and the other q votes with p≥q, what is the probability that the first candidate will be strictly ahead of the second candidate throughout the count? The...
References - Catalan, Eugene. (1844): Note extraite d’une lettre adress´ee. J. Reine Angew. Math., 27:192.
- Stanley, R.P. (1999): Enumerative Combinatorics, Vol. 2. Cambridge University Press. (pp. 219–229)
External links |
Feeds |
Contact