Catalan Number Calculator: Counting Trees, Paths, and Parentheses
About the Author
Marko Šinko
Co-Founder & Lead Developer, AI Math Calculator
Set the Catalan number calculator above to n = 5 and it returns 42. That same 42 counts the binary trees you can build from five nodes, the ways to slice a seven-sided polygon into triangles, the bracketings of a six-factor product, and the handshakes ten people around a table can manage without anyone’s arms crossing. Four problems from four corners of mathematics, one answer. That is not a coincidence anyone planned — it is what makes the sequence 1, 1, 2, 5, 14, 42, 132, 429 worth knowing on sight.
The tool handles the part that trips people up: which index you actually need. A heptagon wants C5, six factors want C5, five nodes want C5, and none of those inputs is the number 5. Pick your problem from the dropdown, type its natural size, and the conversion happens before the arithmetic. Below: why the formula divides by n + 1, the three ways to compute Cn and the one that survives large inputs, and how fast these numbers really grow.
One Count, Eight Problems, Eight Different Indexes
Two counting problems have the same answer for a reason, and the reason is usually a bijection — a way of turning any solution to one problem into exactly one solution of the other. Take a balanced bracket string and read it as instructions for building a tree: every “(” means descend into a child, every “)” means climb back up. Nothing is lost and nothing is duplicated, so the two counts must match. String the bijections together and one sequence ends up counting all of this:
| What you are counting | Index you need | Answer at C₅ = 42 |
|---|---|---|
| Balanced strings of brackets | n = pairs | 5 pairs → 42 strings |
| Binary trees | n = nodes | 5 nodes → 42 trees |
| Triangulating a convex polygon | n = sides − 2 | 7-gon → 42 triangulations |
| Bracketing a product | n = factors − 1 | 6 factors → 42 bracketings |
| Lattice paths under the diagonal | n = grid width | 5 × 5 grid → 42 paths |
| Non-crossing handshakes in a circle | n = people ÷ 2 | 10 people → 42 pairings |
| Non-crossing partitions of a set | n = elements | 5 elements → 42 partitions |
| Permutations sortable by one stack | n = items | 5 items → 42 orders |
Look down the middle column and you can see where the errors come from. Three of those problems take the index straight, one subtracts 1, one subtracts 2, and one halves. Richard Stanley collected more than 200 such interpretations; the OEIS entry A000108 is the canonical reference if you want to check whether your own problem belongs on the list.
Why a Catalan Number Calculator Divides by n + 1
The Catalan number formula looks like an ordinary binomial coefficient with a stray divisor bolted on:
That divisor is not cosmetic, and it is not an average of anything. It falls out of a counting argument known as the reflection method, and the cleanest way to see it is with lattice paths. Suppose you walk from the bottom-left corner of a grid to the top-right using n steps right and n steps up. The total number of routes is just the number of ways to choose which of the 2n steps go right — that is C(2n, n), and any combination calculator will give it to you. For n = 3 that is C(6, 3) = 20.
Now add the restriction that matters: the path must never rise above the diagonal. In bracket language, you may never close a bracket you have not opened. A bad path is one that touches the forbidden line y = x + 1 at some point. Here is the trick — take the first moment a bad path touches that line and reflect everything after it, swapping every right step for an up step. What you get is a path to a different corner, one step over, and the correspondence runs both ways: every bad path becomes exactly one path to that shifted corner, and every path to the shifted corner comes from exactly one bad path.
So the number of bad paths is C(2n, n+1). Subtract:
All paths (n = 3): C(6, 3) = 20
Bad paths: C(6, 4) = 15
Good paths: 20 − 15 = 5 = C₃
Five, and you can list them by hand: ()()(), ()(()), (())(), (()()), ((())). Do the algebra on C(2n, n) − C(2n, n+1) and the whole thing collapses to C(2n, n)/(n + 1). Three quarters of all paths were illegal at n = 3, and it gets worse: at n = 10 only 16,796 of the 184,756 possible paths survive, under 10%. That is why you can never just count arrangements with a permutation calculator and hope the invalid ones are a rounding error.
Three Ways to Compute Cₙ, and When Each One Breaks
Every route below gives the same answer for small n. They part company badly once the numbers grow, and the failure is usually silent — you get a plausible-looking integer that happens to be wrong.
| Method | Cost | Where it breaks |
|---|---|---|
| Factorials: (2n)! / (n!(n+1)!) | O(n) | Worst option. 171! overflows a double, and the intermediates dwarf the answer — C₅ = 42 is computed from 10! = 3,628,800 |
| Central binomial ÷ (n+1) | O(n) | C(2n, n) passes 2⁵³ at n = 29, so floating-point results turn wrong roughly seven terms before Cn itself does |
| Ratio step: Cₙ = Cₙ₋₁ · 2(2n−1)/(n+1) | O(n) | Nothing intermediate exceeds the answer; every division is exact. The default for a single term |
| Segner: Cₙ = Σ Cᵢ · Cₙ₋₁₋ᵢ | O(n²) | Slow, but it is the shape most dynamic-programming problems actually need |
The hard numbers are worth committing to memory if you write code that touches this sequence. C36 = 11,959,798,385,860,453,492 is the first Catalan number too big for a signed 64-bit integer, and C37 breaks unsigned. Long before that, at n = 29, the central binomial C(58, 29) = 30,067,266,499,541,040 has already passed the point where a double-precision float can hold every integer exactly. If your language stores integers as doubles — JavaScript without BigInt, for one — the closed form starts returning confidently wrong values from n = 29 onwards while C29 itself is still perfectly representable. The calculator above sidesteps all of it by running the ratio step on exact big integers, the same reason a factorial calculator has to abandon floats early.
Segner's recurrence earns its keep elsewhere. Written out, C5 = C₀C₄ + C₁C₃ + C₂C₂ + C₃C₁ + C₄C₀ = 14 + 5 + 4 + 5 + 14 = 42. Each term splits a structure at a chosen point: for a bracket string, at the position where the opening bracket finally closes, leaving i pairs inside and n−1−i pairs after. That decomposition is exactly what you implement when a problem asks for optimal matrix-chain bracketing or the best binary search tree — you are not counting the arrangements, you are searching them, and the recurrence tells you the search has Cn leaves. It also has a tidy generating function, (1 − √(1 − 4x))/2x, which a generating function calculator can expand term by term.
The Off-by-One That Turns 42 Into 132
Ask how many ways there are to bracket a product of six factors. The instinct is to reach for C6 = 132. The right answer is C5 = 42, and the reason is the same one that makes handshake problems awkward: the last operation is not free. Six factors need five multiplications, and it is the multiplications you are arranging, not the factors. Same story with the polygon — a triangulated heptagon has seven sides but only five triangles, so it is C5 again, not C7.
Four traps, in the order people fall into them:
- Counting objects instead of operations. Factors, polygon sides and tree leaves all sit one or two above the index. Nodes, bracket pairs and grid width sit exactly on it. The dropdown in the calculator exists for precisely this.
- Forgetting the divisor. C(2n, n) on its own counts every arrangement, legal or not. At n = 5 that is 252 rather than 42 — six times too many.
- Reading “the 5th Catalan number” as C₅. The sequence is conventionally indexed from C₀ = 1, so the fifth term written down is C₄ = 14. When someone says the fifth Catalan number, ask which they mean; papers and textbooks split on it.
- Assuming both children of a tree node are interchangeable. Binary trees count left and right as distinct, which is what makes them Catalan. Drop that distinction and you are counting something else entirely, with a smaller answer.
A quick sanity check catches most of these: Cn for small n runs 1, 1, 2, 5, 14, 42. If your hand count of a four-object problem gives anything other than 5 or 14, you are on the wrong index. And if it lands between two terms — 100, say, which sits between C₆ = 132 and C₅ = 42 — it is not a Catalan problem at all, or you have miscounted. The reverse lookup at the bottom of the calculator answers that question directly.
How Fast They Grow, and Why It Matters for Code
Catalan numbers grow almost exponentially, but not quite. The ratio between consecutive terms is exactly 2(2n − 1)/(n + 1), which is 2.5 at n = 3, 3.714 at n = 20, and 3.96 at n = 100. It climbs toward 4 forever and never arrives. The consequence is the asymptotic form:
That estimate runs about 9/(8n) high, so it is 11% over at n = 10, 5.7% over at n = 20, and just 1.1% over at n = 100 — useful for sizing a problem, useless for an exact answer. The practical numbers: C20 = 6,564,120,420, C50 is 28 digits long, and C100 = 896,519,947,090,131,496,687,170,070,074,100,632,420,837,521,538,745,909,320, all 57 digits of it.
Those figures decide algorithm design more often than people expect. If your program enumerates every binary tree on 20 nodes, you are asking it to produce six and a half billion objects — that job is not slow, it is impossible on a laptop. Thirty nodes puts you at 3.8 quadrillion. Any Catalan-shaped search space has to be pruned or solved with dynamic programming; brute force dies somewhere around n = 15, where 9,694,845 cases are still merely tedious rather than fatal.
Compare that with the Fibonacci sequence, whose ratio settles at 1.618 and which only reaches 6,765 by its twentieth term. Both come from simple recurrences, but the growth constants — 4 against 1.618 — put them in different computational worlds. A Fibonacci-sized search space is something you can walk through. A Catalan-sized one you have to be clever about.
