CatalanNumber

The nth Catalan number $C_n$, counting balanced bracket sequences, binary trees, polygon triangulations, and many other structures of size n.

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaCatalan number↗MathWorldCatalanNumber↗WikidataQ270513↗nLabCatalan number↗DLMF26.5.E1↗OEISA000108↗Wolfram LanguageCatalanNumber!↗

CatalanNumber(n)the nth Catalan number $C_n$.

SageMathcatalan_number(n)!↗SymPycatalan(n)↗JuliaCombinatorics.catalannum(n)

Typed signatures

Type	Package	Applies
(integer) -> integer	compute-engine	always
(number) -> number	analyticreplaces compute-engine	always
(any) -> any	number-theoryreplaces analytic	always

Domain: Combinatorics

Details

• The Catalan numbers have the closed form $C_n = \frac{1}{n+1}\binom{2n}{n}$.
• They satisfy the recurrence $C_{n+1} = \sum_{i=0}^{n} C_i\,C_{n-i}$ with $C_0 = 1$.
• $C_n$ is the number of monotonic lattice paths from one corner of an $n \times n$ grid to the opposite corner that stay below the diagonal.
• compute-engine extends $C_n$ to real and complex arguments through the Binomial gamma-function form $C_n = \Gamma(2n+1)/(\Gamma(n+1)\,\Gamma(n+2))$. At a negative integer it instead follows Wolfram's own $C_n = \binom{2n}{n} - \binom{2n}{n+1}$ with $\binom{n}{k} = 0$ for a negative integer $k$, giving $C_{-1} = -1$ and $C_n = 0$ for every integer $n \le -2$ (the smooth Gamma-ratio limit disagrees at $n=-1$, giving $-\tfrac12$ -- see the divergence note on that example).

Examples

2 more kept as data, checked against the oracles

Basic #

live ↗

In$\mathrm{CatalanNumber}(0)$Out$1$

live ↗

In$\mathrm{CatalanNumber}(1)$Out$1$

live ↗

In$\mathrm{CatalanNumber}(5)$Out$42$

live ↗

In$\mathrm{CatalanNumber}(10)$Out$16\,796$

live ↗

In$\mathrm{CatalanNumber}(30)$Out$3\,814\,986\,502\,092\,304$

Scope #

$C_{-1} = -1$, from $\binom{2n}{n} - \binom{2n}{n+1}$ at $n=-1$ ($\binom{-2}{-1} - \binom{-2}{0} = 0 - 1$)

live ↗

In$\mathrm{CatalanNumber}(-1)$Out$-1$

$C_n = 0$ for every integer $n \le -2$ -- both $\binom{2n}{n}$ and $\binom{2n}{n+1}$ have a negative lower index there

live ↗

In$\mathrm{CatalanNumber}(-2)$Out$0$

live ↗

In$\mathrm{CatalanNumber}(-5)$Out$0$

Threads element-wise over a list, as Wolfram's Listable heads do

live ↗

In$\mathrm{CatalanNumber}(\bigl\lbrack1, 2, 3, 4\bigr\rbrack)$Out$\bigl\lbrack1, 2, 5, 14\bigr\rbrack$

Half-integer arguments evaluate exactly through $C_n = \frac{\Gamma(2n+1)}{\Gamma(n+1)\,\Gamma(n+2)}$

live ↗

In$\mathrm{CatalanNumber}(\frac{5}{2})$Out$\frac{1\,024}{105π}$

Real arguments evaluate as $\frac{\Gamma(2n+1)}{\Gamma(n+1)\,\Gamma(n+2)}$

live ↗

In$\mathrm{CatalanNumber}(2.3)$Out$2.590\,352\,154\,019\,323\,3$

Complex arguments evaluate through the same Gamma form

live ↗

In$\mathrm{CatalanNumber}(1.2+i)$Out$0.730\,728\,624\,207\,283\,9+0.569\,846\,406\,969\,342\,5i$

$C_{1/2} = \frac{8}{3\pi}$ by analytic continuation

live ↗

In$\mathrm{CatalanNumber}(\frac{1}{2})$Out$\frac{8}{3π}$

An Interval argument gives an enclosing Interval

live ↗

In$\mathrm{CatalanNumber}(\mathrm{Interval}(0.5, 0.6))$Out$\mathrm{Interval}(0.848\,826\,363\,156\,775\,1, 0.862\,540\,968\,873\,452\,3)$

Applications #

The 5 ways to balance 3 pairs of parentheses

live ↗

In$\mathrm{CatalanNumber}(3)$Out$5$

The 14 triangulations of a hexagon, and the 14 binary trees with 4 leaves. See Binomial

live ↗

In$\mathrm{CatalanNumber}(4)$Out$14$

live ↗

In$\mathrm{Assuming}(n∈ℤ∧n≥0, \mathrm{FullSimplify}(\mathrm{CatalanNumber}(n)=\frac{2^{2n+1}(2n-1)!!}{(2n+2)!!}))$Out$\mathrm{CatalanNumber}(n)=\frac{(2n-1)!!×2^{2n+1}}{(2n+2)!!}$

Properties #

Closed form $C_n = \frac{1}{n+1}\binom{2n}{n}$, here at $n = 5$

live ↗

In$\frac{\binom{2×5}{5}}{5+1}$Out$42$

Equivalently $C_n = \binom{2n}{n} - \binom{2n}{n+1}$

live ↗

In$\binom{10}{5}-\binom{10}{6}$Out$42$

The consecutive ratio is $\frac{C_{n+1}}{C_n} = \frac{2(2n+1)}{n+2}$

live ↗

In$\frac{\mathrm{CatalanNumber}(6)}{\mathrm{CatalanNumber}(5)}$Out$\frac{22}{7}$

Segner's recurrence $C_{n+1} = \sum_{i=0}^{n} C_i\,C_{n-i}$, here at $n = 3$

live ↗

In$\mathrm{CatalanNumber}(4)=\sum_{i=0}^3\mathrm{CatalanNumber}(i)\mathrm{CatalanNumber}(3-i)$Out$\mathrm{True}$

The Catalan generating function $\frac{1-\sqrt{1-4x}}{2x}$

live ↗

In$\mathrm{GeneratingFunction}(\mathrm{CatalanNumber}(n), n, x)$Out$\frac{1-\sqrt{1-4x}}{2x}$

Zero at negative integers

live ↗

In$\mathrm{CatalanNumber}(-10)$Out$0$

Known value · Wolfram MathematicalFunctionData, CatalanNumber

Negative index gives zero, not a pole

live ↗

In$\mathrm{CatalanNumber}(-9)$Out$0$

Known value · Wolfram MathematicalFunctionData, CatalanNumber

Vanishes for a negative integer index

live ↗

In$\mathrm{CatalanNumber}(-8)$Out$0$

Known value · Wolfram MathematicalFunctionData, CatalanNumber

Catalan numbers are zero below index 0

live ↗

In$\mathrm{CatalanNumber}(-7)$Out$0$

Known value · Wolfram MathematicalFunctionData, CatalanNumber

Another negative index, another zero

live ↗

In$\mathrm{CatalanNumber}(-6)$Out$0$

Known value · Wolfram MathematicalFunctionData, CatalanNumber

Negative arguments give 0

live ↗

In$\mathrm{CatalanNumber}(-4)$Out$0$

Known value · Wolfram MathematicalFunctionData, CatalanNumber

Zero at every negative integer, not just $-1$

live ↗

In$\mathrm{CatalanNumber}(-3)$Out$0$

Known value · Wolfram MathematicalFunctionData, CatalanNumber

live ↗

In$\mathrm{DifferenceRootReduce}(\mathrm{CatalanNumber}(k), k)$Out$\mathrm{DifferenceRoot}((y, n)↦\begin{cases}(n+2)y(n+1)-2(2n+1)y(n)=0\\y(0)=1\end{cases})\lhd k$

Neat examples #

They grow fast: $C_{15}$ already passes nine million

live ↗

In$\mathrm{CatalanNumber}(15)$Out$9\,694\,845$

About

Examples	33
Checked against	Wolfram Language 31 agree1 differ1 unevaluatedSageMath 22 agree2 differ4 errorSymPy 27 agree3 differmpmath 27 agree1 errormathlib4 10 agreeJulia 13 agree1 differ14 errorOscar 3 agreeRust 3 agree1 differ
Crosswalk	WikipediaMathWorldWikidatanLabDLMFOEISWolfram LanguageSageMathSymPyJulia

Implementation

mappedwolframpackages/oracle/src/mappings.ts

mappedsympypackages/oracle/src/mappings.ts

mappedsagepackages/oracle/src/mappings.ts

mappedjuliapackages/oracle/src/mappings.ts

mappedmathlib4packages/oracle/src/mappings.ts

mappedmpmathpackages/oracle/src/mappings.ts

binomial(2n, n)/(n + 1), continued by the gamma function.

See also: Binomial, BellNumber