catalan(): count recursive structures

catalan(n) returns the nth Catalan number. This sequence begins 1, 1, 2, 5, 14, 42 and counts many apparently different structures: correctly nested parentheses, binary search tree shapes, polygon triangulations, and non-crossing pairings.

Formula and example

For a non-negative integer n, the value is binomial(2n, n)/(n + 1). catalan(3) is 5, which is the number of valid ways to arrange three matched pairs of parentheses. The numbers grow quickly, so exact integer arithmetic is preferable for larger n.

Related combinatorics

combinations() computes the central coefficient in the formula. For other counting families, see combinations(), bernoulli(), and stirlingS2(). factorial() helps derive the equivalent factorial form.

Valid input

n must be a non-negative integer. A fractional or negative index does not identify a standard Catalan number. Do not confuse a count of structures with a probability; normalize separately if needed.