Catalan Numbers Calculator

Compute Catalan numbers and explore the structures they count: trees, triangulations, parentheses, and lattice paths.

Results are calculated automatically as you enter data.

Sequence controls

Index n Interpretation Examples shown

Formula and recurrence

Visualization

Recursive breakdown

Sequence table

Disclaimer: All tools on this site are intended for educational and informational purposes only. This calculator normalizes the index and example limit by rounding and clamping them to their supported ranges. The supported Catalan count is computed exactly as an integer; this is not professional advice. See our Terms of Use.

Assumptions and limitations

This Catalan Numbers Calculator is for general educational use. The index and example limit may be rounded or clamped to the supported ranges. Catalan counts are exact integer values, but the calculator is not guaranteed to be error-free. Check the formulas, assumptions, and input values before relying on the result. Use of this calculator is subject to our Terms of Use.

▼ See explanations and tips below ▼

Related Calculators

What Are Catalan Numbers?

Catalan numbers are a sequence of whole numbers that count many different kinds of ordered, noncrossing, or well-balanced structures. The sequence begins:

$$ 1,\ 1,\ 2,\ 5,\ 14,\ 42,\ 132,\ 429,\ \ldots $$

The $n$th Catalan number is usually written as $C_n$ or $C(n)$. The index $n$ is a nonnegative integer: $0, 1, 2, 3, \ldots$. Even though the sequence is only one list of numbers, it appears in many counting problems that look different at first.

For example, the same value $C_n$ can count:

valid strings made from $n$ pairs of parentheses,
lattice paths with $n$ north steps and $n$ east steps that stay on one side of a diagonal,
triangulations of a convex polygon with $n+2$ sides,
mountain ranges with $n$ upward steps and $n$ downward steps that never dip below the baseline.

That is what makes Catalan numbers useful in combinatorics. They reveal that several different-looking problems share the same underlying structure.

Why Catalan Numbers Matter

Catalan numbers are a classic example of how mathematicians count structured possibilities without listing every possibility one by one. They are especially useful in discrete mathematics, combinatorics, computer science, and algorithm design because they count objects built from nested or recursive choices.

A parenthesis string is a simple example. With $3$ pairs of parentheses, there are only $5$ valid arrangements. With $8$ pairs, there are $1430$. The count grows quickly, so a formula or recurrence is much more useful than manual listing.

Catalan numbers also help students connect several important ideas: binomial coefficients, recursion, bijections, lattice paths, balanced strings, polygon triangulations, and generating functions. Understanding one Catalan interpretation often makes the others easier to learn.

Key Terms to Know

Catalan number: A number in the sequence $C_0, C_1, C_2, \ldots$ that counts many standard combinatorial structures.
Index $n$: The nonnegative integer that selects which Catalan number to compute.
Binomial coefficient: The number $\binom{m}{r}$, read as “$m$ choose $r$,” which counts ways to choose $r$ items from $m$ items.
Central binomial coefficient: The coefficient $\binom{2n}{n}$, which appears in the closed form for $C_n$.
Recurrence relation: A rule that defines a value using earlier values in the same sequence.
Balanced parentheses: A string where every opening parenthesis is matched correctly with a later closing parenthesis.
Dyck path: A path made of balanced up/down or north/east steps that never crosses below, or above depending on convention, the allowed boundary.
Triangulation: A way to divide a polygon into triangles using noncrossing diagonals.

How Catalan Numbers Work

The most common closed form for the $n$th Catalan number is:

$$ C_n = \frac{1}{n+1}\binom{2n}{n} $$

The same formula can also be written with factorials:

$$ C_n = \frac{(2n)!}{n!(n+1)!} $$

Where:

$n$ is a nonnegative integer,
$C_n$ is the $n$th Catalan number,
$\binom{2n}{n}$ is the central binomial coefficient,
$n!$ means the product $n \times (n-1) \times \cdots \times 1$, with $0! = 1$.

A useful way to understand this formula is through paths. There are $\binom{2n}{n}$ ways to arrange $n$ steps of one type and $n$ steps of another type. Catalan numbers count only the arrangements that stay within the required boundary, such as paths that do not cross the diagonal or parenthesis strings that never close more parentheses than they have opened.

Catalan numbers also satisfy a recurrence:

$$ C_0 = 1 $$

$$ C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}\quad \text{for } n \ge 1 $$

This recurrence says that a Catalan structure of size $n$ can often be split into a left part of size $k$ and a right part of size $n-1-k$. For each split, multiply the number of choices for the left part by the number of choices for the right part, then add all possible splits.

For example, for $n=4$:

$$ C_4 = C_0C_3 + C_1C_2 + C_2C_1 + C_3C_0 $$

Using $C_0=1$, $C_1=1$, $C_2=2$, and $C_3=5$:

$$ C_4 = 1\times5 + 1\times2 + 2\times1 + 5\times1 = 14 $$

The closed form is efficient for getting the exact count. The recurrence is useful for understanding why the same sequence appears in recursive structures such as valid parentheses, binary trees, and polygon triangulations.

Examples of Catalan Numbers in Practice

Example 1: Valid Parentheses with 3 Pairs

Suppose $n=3$. The closed form gives:

$$ C_3 = \frac{1}{3+1}\binom{6}{3} $$

$$ C_3 = \frac{1}{4}\times 20 = 5 $$

So there are $5$ valid strings made from $3$ pairs of parentheses:

((()))
(()())
(())()
()(())
()()()

Each string is balanced because every closing parenthesis has a matching earlier opening parenthesis.

Example 2: Triangulating a Polygon

For the triangulation interpretation, $C_n$ counts triangulations of a convex polygon with $n+2$ sides. If $n=4$, the polygon has:

$$ n+2 = 4+2 = 6 $$

So $C_4$ counts triangulations of a convex hexagon:

$$ C_4 = \frac{1}{5}\binom{8}{4} $$

$$ C_4 = \frac{70}{5} = 14 $$

There are $14$ ways to divide a convex hexagon into triangles using noncrossing diagonals.

Example 3: The Empty Case $n=0$

Catalan numbers start with $C_0=1$. The closed form agrees:

$$ C_0 = \frac{1}{0+1}\binom{0}{0} = 1 $$

This may feel surprising at first because there is “nothing” to arrange. In combinatorics, the empty structure is often counted as one valid structure. For Catalan numbers, $C_0=1$ also makes the recurrence work cleanly, because larger structures can be built from smaller empty and nonempty parts.

How to Interpret the Result

The result $C(n)$ is the exact number of Catalan-counted structures for the normalized index $n$. It is a count, not a measurement, so it has no physical unit.

A small result means the structures can usually be listed and checked by hand. For example, $C_3=5$ is easy to display as parenthesis strings or paths. A large result means there are many possible structures, and the exact count is more useful than a complete list.

Changing the interpretation changes the way the structures are shown, but it does not change the Catalan number itself. For the same $n$, valid parentheses, diagonal-safe paths, triangulations of an $(n+2)$-gon, and mountain ranges all have the same count $C_n$.

The recurrence breakdown shows where the count comes from. Each row represents one split of the structure into two smaller Catalan parts. The contribution for a split is the product of the two smaller counts, and the full Catalan number is the sum of all those contributions.

Generated examples are samples controlled by the selected interpretation and example limit. When the exact count is larger than the number of examples shown, the examples list is not exhaustive.

Common Mistakes and Misconceptions

One common mistake is thinking the selected interpretation changes the numeric answer. It does not. The interpretation changes the examples and visualization, while the value $C_n$ stays the same for the same index $n$.

Another mistake is confusing $n$ with the number of polygon sides in the triangulation model. The triangulation interpretation uses an $(n+2)$-gon. For example, $n=4$ corresponds to a hexagon, not a quadrilateral.

It is also easy to assume that a displayed examples list contains every possible structure. That is only true when the exact count is no larger than the selected example limit and the example generation is not capped.

Decimals and negative values are not separate Catalan-number cases in this calculator. Catalan numbers are indexed by nonnegative integers. Decimal inputs are rounded to an integer, and negative inputs are normalized to $0$.

Finally, $C_0=1$ should not be read as saying there is one visible object to draw. It means there is one empty structure, which is the standard base case for the sequence.

When to Use Catalan Numbers

Use Catalan numbers when a problem involves counting structured objects that must remain balanced, nested, ordered, or noncrossing.

Common uses include:

counting valid parenthesis strings with $n$ pairs,
counting paths that stay on the allowed side of a diagonal or baseline,
counting triangulations of a convex polygon,
studying recursive structures in discrete mathematics,
comparing different combinatorial models that turn out to have the same count.

Catalan numbers are especially helpful when listing every possible arrangement would be slow or error-prone.

Limitations and Things to Keep in Mind

Catalan numbers apply to nonnegative integer indices. They do not normally describe negative, fractional, or symbolic indices in the elementary counting interpretations used here.

This calculator normalizes inputs before computing. The index $n$ is rounded to the nearest integer and clamped to the range $0$ through $100$. The example limit is rounded to the nearest integer and clamped to the range $1$ through $40$.

The exact Catalan count is shown as an integer. The count is not rounded, abbreviated, or estimated. Very large values may be long because Catalan numbers grow quickly.

Examples and visualizations are more limited than the exact count. For responsiveness, generated examples and visualizations are capped at $n=30$. When $n$ is greater than $30$, the exact count still reflects the entered index after normalization, but examples and visual output may be capped or unavailable.

Visualization is not available for every case. The parenthesis interpretation is text-based, $n=0$ has no visible nonempty structure to draw, and graph download depends on browser support for preparing the image file.

How to Use This Calculator

Enter the Catalan index $n$.
Choose an interpretation: valid parentheses, lattice paths, triangulations, or mountain ranges.
Enter the maximum number of examples to generate, from $1$ to $40$.
Review the exact $C(n)$ result and the metric cards.
Use the formula cards, recurrence breakdown, and sequence table to understand how the result fits into the Catalan sequence.
Select a generated example to update the visualization when a visual mode is available.
Use the graph download option to save the displayed visualization as a PNG when available.

Frequently Asked Questions

What is the first Catalan number?

The sequence starts with $C_0=1$. This represents the empty structure and serves as the base case for the recurrence. The next values are $C_1=1$, $C_2=2$, $C_3=5$, and $C_4=14$.

Why do parentheses, paths, polygons, and mountains have the same count?

These models can be matched through structure-preserving correspondences. For example, an opening parenthesis can be treated like an upward or northward step, while a closing parenthesis can be treated like a downward or eastward step. The rule that parentheses stay balanced becomes the rule that the path stays within its allowed boundary.

Does $C_n$ count all paths from one corner of a grid to another?

No. The central binomial coefficient $\binom{2n}{n}$ counts all arrangements of $n$ steps of each type. The Catalan number counts only the valid paths that stay on the required side of the diagonal or baseline.

Why does the recurrence multiply smaller Catalan numbers?

For a fixed split, the left part and right part can be chosen independently. If the left part has $C_k$ possibilities and the right part has $C_{n-1-k}$ possibilities, that split contributes $C_kC_{n-1-k}$ structures. Adding over all splits gives $C_n$.

Why are examples and visualizations capped?

Catalan numbers grow quickly, so generating and drawing all structures can become expensive even when the exact count is easy to display. The cap keeps the interface responsive while still showing the exact Catalan number for supported indices.

Sources and References

Books

Richard P. Stanley. Catalan Numbers. Cambridge University Press, 2015. Introductory properties and catalog of Catalan-counted structures. ISBNs 9781107075092, 9781107427747; DOI: https://doi.org/10.1017/CBO9781139871495.
Thomas Koshy. Catalan Numbers with Applications. Oxford University Press, 2009. Chapter 5, “Catalan Numbers,” pp. 103–148. ISBN 9780195334548; DOI for chapter: https://doi.org/10.1093/acprof:oso/9780195334548.003.0005.
Steven Roman. An Introduction to Catalan Numbers. Compact Textbooks in Mathematics, Birkhäuser Cham/Springer, 2015. Chapters “Dyck Words,” “The Catalan Numbers,” and “Catalan Numbers and Paths,” pp. 7–22. DOI: https://doi.org/10.1007/978-3-319-22144-1.

Online and Educational Sources

Richard Grassl and Oscar Levin. “The Catalan Numbers.” More Discrete Mathematics via Graph Theory, Open Math Books, accessed June 27, 2026. https://discrete.openmathbooks.org/more/mdm/sec_basic-catalan.html
OEIS Foundation. “A000108 — Catalan Numbers.” The On-Line Encyclopedia of Integer Sequences, accessed June 27, 2026. https://oeis.org/A000108
Eric W. Weisstein. “Catalan Number.” Wolfram MathWorld, accessed June 27, 2026. https://mathworld.wolfram.com/CatalanNumber.html