Probability & Combinatorics
Advanced

Catalan Number

Counts many recursive structures such as balanced parentheses.

Formula

Cn=1n+1(2nn)C_n = \frac{1}{n+1}\binom{2n}{n}

Variables

nIndex

Example

C_3 = 5

Did You Know?

Catalan numbers count binary trees, paths, and polygon triangulations.

countingsequences