Maths & numbers

Catalan number calculator

Count balanced parentheses strings with n pairs, among other Catalan structures.

Your numbers

Calculated on your device. Your inputs aren’t sent to us.

Your result

Ready when you are

Enter your inputs and select Calculate.

Report an issue

Behind the numbers

How this calculation works

A balanced sequence never closes more parentheses than it has opened in any prefix.

THE FORMULACₙ = binom(2n,n)/(n+1)

A worked example

Five pairs can form 42 balanced strings.

Good to know

The index starts at zero.

Count balanced parentheses by pair count

The Catalan number Cₙ counts balanced strings with n opening and n closing parentheses, where every prefix has at least as many openings as closings. For n = 2, the valid strings are (()) and ()(), giving C₂ = 2. The string )( is invalid because its first prefix closes before anything has opened.

For the default n = 5, evaluate C(10,5)/(5 + 1) = 252/6 = 42. The index specifies pairs, so the strings have ten symbols. The tool computes an exact integer count, rather than generating and checking every candidate string.

The two balanced parentheses strings with two pairs are nested and consecutive(())()()C₂ = 2 balanced stringsFive pairs give C₅ = 42
Both strings have two opening and two closing symbols. Every prefix has at least as many openings as closings.

Match the index to the structure being counted

Catalan numbers appear in several settings with different descriptions of the index. They count full binary tree shapes with n internal nodes and triangulations of a convex polygon with n + 2 vertices. Before substituting a size, translate it into the index used by the relevant correspondence.

The Derangement count calculator also counts restricted permutations, but its no-fixed-position rule is different from the prefix-balance rule used here. For parentheses there are C(2n,n) strings with equal opening and closing totals, and only Cₙ of them satisfy every prefix constraint. Equal overall totals alone are therefore insufficient. The empty string counts as one balanced string, so C₀ = 1.

A few questions, answered

Does C₅ mean five symbols?

It means five parenthesis pairs, or ten symbols, for the balanced-parentheses interpretation.

Can I swap opening and closing symbols arbitrarily?

No. A valid string must have a nonnegative opening-minus-closing count at every prefix and end at zero.

Find your calculator

Start typing to explore the library.