The Catalan numbers 
, indexed by nonnegative
integers 
, arise in tree enumeration
problems of the type, "In how many ways can a regular
n-gon be divided into 
triangles if different orientations
are counted separately?" (Euler's
polygon division problem). For 
, the solution is the Catalan
number 
(Pólya 1956; Dörrie 1965; Honsberger 1973; Borwein and Bailey 2003, pp. 21-22),
as graphically illustrated above (Dickau).
Catalan numbers are commonly denoted 
(Graham et al. 1994; Stanley 1999b, p. 219;
Pemmaraju and Skiena 2003, p. 169; this work) or 
(Goulden and Jackson 1983, p. 111), and less commonly
(van Lint and Wilson 1992, p. 136).
Catalan numbers are implemented in the Wolfram Language as CatalanNumber[n].
The first few Catalan numbers for 
, 2, ... are 1, 2, 5, 14, 42,
132, 429, 1430, 4862, 16796, ... (OEIS A000108).
Explicit formulas for 
include
 |  |  |
(1)
|
 |  |  |
(2)
|
 |  |  |
(3)
|
 |  |  |
(4)
|
 |  |  |
(5)
|
 |  |  |
(6)
|
 |  |  |
(7)
|
for 
, except that the expression containing 
requires 
, where 
is a binomial coefficient, 
is a factorial, 
is a double factorial,
is the gamma
function, and 
is a hypergeometric function.
The Catalan numbers may be generalized to the complex plane, as illustrated above.
Sums giving 
include
 |  |  |
(8)
|
 |  |  |
(9)
|
 |  |  |
(10)
|
 |  |  |
(11)
|
 |  | ![sum_(k=0)^(|_n/2_|)[(n-2k+1)/(n-k+1)(n; n-k)]^2,](/images/equations/CatalanNumber/Inline55.svg) |
(12)
|
where the first three sums require 
, the last two also hold
at 
, and 
is the floor function.
A product for 
is given by
 |
(13)
|
The Catalan numbers are the inverse binomial transform of the Riordan numbers.
Sums involving 
include the generating
function
 |  |  |
(14)
|
 |  |  |
(15)
|
for 
(OEIS A000108), and the exponential
generating function
![e^(2x)[I_0(2x)-I_1(2x)]](/images/equations/CatalanNumber/Inline68.svg) |  |  |
(16)
|
 |  |  |
(17)
|
for every complex number 
(OEIS A144186 and A144187), where 
is a modified
Bessel function of the first kind, as well as
 |  |  |
(18)
|
 |  |  |
(19)
|
where the quotient in the second identity has limiting value 1 at 
. That identity holds for every complex
number 
.
The asymptotic form for the Catalan numbers is
 |
(20)
|
as the real number 
(Vardi 1991, Graham et al. 1994).
The numbers of decimal digits in 
for 
, 1, ... are 1, 5, 57, 598,
6015, 60199, 602051, 6020590, ... (OEIS A114466).
The ratios of these digit counts to 
converge to 
(OEIS A114493).
A recurrence relation for 
is obtained from
 |
(21)
|
so
 |
(22)
|
Segner's recurrence formula (Segner 1761) gives the solution to Euler's polygon division problem
 |
(23)
|
With 
and the recurrence applied for 
, the solution is 
for 
.
From the definition of the Catalan number, every prime divisor of 
is less than 
. On the other hand, 
for 
. Therefore, 
is the largest Catalan prime,
making 
and 
the only Catalan primes. (Of course, much more than
this can be said about the factorization of
.)
The only odd Catalan numbers are those of the form 
for integer 
. The first few are therefore
1, 1, 5, 429, 9694845, 14544636039226909, ... (OEIS A038003).
For integer 
, the odd
Catalan number 
ends in 5 unless the quinary (base
5) expansion of 
uses only the digits 0, 1, and 2. Its first few final digits, starting at 
, are 1, 5, 9, 5, 9, 5, 9, 7,
5, 5, 5, 5, 5, ... (OEIS A094389); the sequence
also has initial value 1 at 
. For 
, the exceptions to a final digit
of 5 occur only at 
, 3, 5, 7, and 8.
The Catalan number 
counts the binary bracketings of 
letters, for 
(Catalan's problem).
For 
, 
counts Dyck paths with 
upsteps and 
downsteps, ballot problem
sequences with 
votes for each candidate in which the first candidate never trails, full ordered
binary trees with 
internal vertices, rooted
plane trees with 
edges, and noncrossing handshakes between 
pairs of people at fixed cyclic positions around a round table.
It also counts formal bracketings of an exponential expression with 
ordered operands and 
exponentiation signs. Equivalently,
these objects include mountains with 
upstrokes and 
downstrokes which never fall below their starting level, and
trivalent planted planar trees with 
internal trivalent vertices
and 
leaves other than the plant.
For 
, 
also counts the admissible diagonals across all positive-integral
multiplicative frieze patterns with 
rows, including the two bounding rows of 1s, with horizontal
position and direction fixed (Conway and Guy 1996, pp. 96-106; Stanley 1999b,
pp. 231 and 269). The number of abstract flexagon
configurations of order 
in the Oakley-Wisner model is 
, for 
: these are ordered pairs
of pats of total degree 
, before configurations related
by pinches or rotations are identified (Oakley and Wisner 1957).
A generalization of the Catalan numbers is defined by
 |  |  |
(24)
|
 |  |  |
(25)
|
for integers 
and 
, with 
(Klarner 1970, Hilton and Pedersen 1991). The usual
Catalan numbers 
are a special case with 
. 
gives the number of full ordered 
-ary trees with 
internal nodes, the number
of ways of associating 
applications of a given 
-ary operator, the number of ways
of dividing a convex polygon with 
sides into 
interior-disjoint 
-gons with nonintersecting polygon
diagonals, and the number of p-good paths
from (0, 
) to 
(Hilton and Pedersen 1991).
A further generalization is obtained as follows. Let 
be an integer 
, let 
with 
, and let 
be an integer with 
. Then define 
and let 
be the number of p-good
paths from (1, 
) to 
(Hilton and Pedersen 1991). For 
, formulas for 
include the generalized Jonah
formula
 |
(26)
|
and the explicit formula
 |
(27)
|
A recurrence relation is given by
 |
(28)
|
where 
is a fixed positive integer with 
, 
, and the sum is over positive
integers 
with 
(Hilton and Pedersen 1991).
