Catalan Numbers
The Catalan numbers count a remarkable range of combinatorial objects: balanced parentheses, full binary trees, polygon triangulations, monotonic lattice paths that don't cross the diagonal, and ways to multiply a chain of matrices — all share the same count C(n). C(n) = (2n)! / ((n+1)! · n!) = C(2n, n) / (n+1), with the recurrence C(0) = 1, C(n) = 2(2n−1)·C(n−1) / (n+1). This tool computes C(n) exactly with big integers, lists the first values, and lists the well-formed parentheses strings with n pairs for small n. Runs locally in your browser.
Input
Result
Balanced parentheses with n pairs
C(n) = (2n)! / ((n+1)! · n!) — the n-th Catalan number. The recurrence C(n) = 2(2n−1)·C(n−1) / (n+1) (with C(0) = 1) computes it in O(n) with exact integer division. Catalan numbers count, among dozens of other things, the number of well-formed strings of n pairs of parentheses (e.g. n = 3 → ((())) (()()) (())() ()(()) ()()(), count 5 = C(3)), full binary trees with n+1 leaves, and triangulations of a convex (n+2)-gon — all enumerated by the same sequence 1, 1, 2, 5, 14, 42, 132, 429, 1430, …. The listing of parentheses strings is generated recursively and capped for readability (Catalan numbers grow as ~4ⁿ/n^(3/2), so only small n are listable). Pairs with the Combinatorics, Derangements, and Integer Partitions tools. Everything runs locally — nothing leaves your browser.