Catalan number

The Catalan numbers or Catalan numbers form a sequence of natural numbers, which occurs in many problems of combinatorics and plays a similarly important role as the binomial coefficients or the Fibonacci numbers. They are named after the Belgian mathematician Eugène Charles Catalan.

The sequence of Catalan numbers C0, C1, C2, C3, ... starting with

The Catalan numbers are given by

Wherein the central binomial coefficient is. To obtain, that the formula is equivalent to

Is thus actually delivers only integers.

Historical

The numbers of this sequence have been described already in 1751 by Leonhard Euler in a letter to Christian Goldbach. Johann Andreas Segner of 1758 was a recurrence formula to Euler in the summary to Segner article indicated the solution. Collateral received from Johann Friedrich Pfaff general Abzählungsaufgabe sparked 1795 Nikolaus foot. In the years 1838 and 1839, Gabriel Lamé, Olinde Rodrigues, Jacques Binet and Eugène Catalan attacked the question up again. Eugen net resulted in his 1901 published textbook Combinatorik back the numbers on Catalan.

Properties

Euler studied the number of ways a convex n-gon into triangles by diagonals to divide ( triangulation). This number is. For example, there are five possible triangulations of a pentagon:

Euler gave in his letter to Goldbach in 1751 (see History ), the explicit formula

And the formula

For the generating function of, in particular

As a description of the growth behavior.

Direct from the formula ( *) follows

It is also the recursion formula ( Segner 1758)

For example.

Another recursion is

Since all prime factors of, see formula (*), are smaller than and are, and the only Catalan numbers also prime numbers. The formula also shows that, by every prime number between and exactly once is divisible if and only odd, though. Represents an integer

From the set of the Wolstenholme congruence follows

For every prime number, for Wolstenholme primes the congruence applies (mod p4 ) for the primes 2 and 3, it shall (mod p2).

In particular, and for each prime and integer.

By inserting the Stirling formula we obtain for the asymptotic behavior of the Catalan numbers

Other interpretations

The Catalan numbers occur in many Abzählungsaufgaben, which are graph-theoretical Abzählungen of trees on. So is the number of

  • Beklammerungen a product, occur in the n multiplications, or, equivalently, with n 1 factors, so always carry only the multiplication of two factors (Catalan 1838). For example, because all sorts of Beklammerungen are and.
  • One-dimensional random walks from 0 to 2n with start and end points in 0, so that the path is never below the x - axis ( so-called Dyck paths after Walther von Dyck ). For example, because all possible paths are:
  • Ordered full binary trees with 2n 1 nodes or, equivalently, with n 1 leaves ( = Discover ). The following diagram shows one of such binary trees = 1430 for n = 8:
  • Possible courses of counting in an election in which candidate A is never counted after each voice behind candidate B if both candidates each receive n votes and ballots are sequentially taken out of the ballot box and counted. For example, for n = 2 would be the possible contraction episodes, meet the condition, ABAB and AABB.
  • Ways in which 2n people sitting at a round table, in pairs across the table to shake hands without being crossed arms.
Eugen Netto Convex set Wolstenholme's theorem Modular arithmetic Stirling's approximation Matrix chain multiplication Peter Hilton Richard P. Stanley Wolfram Research
169676
de