Catalan Numbers: The Sequence That Counts Everything

Stack-sortable permutations. A permutation is called stack-sortable if running it through a single stack (push, pop, in the right order) puts it back in ascending order. The count of stack-sortable permutations of n elements is, again, the n-th Catalan number — a fact used in analyzing sorting networks and railway-yard shunting puzzles (literally: 19th-century railway switching problems are mathematically identical to this).

RNA secondary structure. In molecular biology, an RNA strand folds so that certain bases pair up with each other, forming loops and stems. When researchers restrict attention to "non-crossing" pairings — the biologically dominant case, since crossing base pairs create structures called pseudoknots that are rarer and harder to model — the number of possible folding patterns for a strand follows a Catalan-like recurrence. It's one of the reasons Catalan numbers appear directly in bioinformatics papers on RNA secondary-structure prediction.

Non-crossing partitions and handshakes. Imagine 2n people sitting around a circular table, and everyone wants to shake hands with exactly one other person, but no two handshakes are allowed to cross each other (picture it geometrically — no arm reaching over another arm). The number of ways to pair everyone up without any crossings is the n-th Catalan number. Swap "handshakes" for chord diagrams, telephone-wiring layouts, or non-crossing partitions of a set, and you get the same count.

The Details

A brief, slightly contested history. The story usually credited to European mathematics begins with Leonhard Euler, who in 1751 wrote to Christian Goldbach about counting the number of ways to slice a convex polygon into triangles using non-crossing diagonals — the "polygon triangulation problem." Euler worked out the values for small polygons by hand and guessed at a general pattern but couldn't prove it. The Hungarian mathematician Johann (János) Segner supplied the recurrence relation in 1758, and with further help from Goldbach, a full proof followed in 1759. So for nearly a century, this sequence was informally "Euler's numbers" or tied to the triangulation problem specifically.

It was the Belgian-French mathematician Eugène Charles Catalan (1814–1894), a student of Joseph Liouville at the École Polytechnique in Paris, who in 1838 rediscovered the sequence in a completely different guise — counting the ways to insert parentheses into a string of symbols to make every multiplication unambiguous (the same "balanced parentheses" idea above). Catalan wrote the formula in essentially its modern closed form and, whether through the influence of his later career at the University of Liège or the utility of his combinatorial framing, the name stuck: mathematicians started calling them "Catalan numbers" even though Euler and Segner had gotten there first.

There's an even earlier chapter, largely unknown in the West until recently: the Mongolian-Chinese mathematician Ming Antu (明安圖), working in the 1730s, derived infinite series involving what we now recognize as Catalan-number coefficients while studying nested radical expansions related to trigonometry. His work was compiled and published posthumously in 1839, and the connection to Catalan numbers wasn't formally identified by scholars until 1988. So depending on how you count, the "Catalan" numbers were independently found in China roughly two decades before Euler ever wrote to Goldbach about them.

Visualizing the growth. Picture a "mountain range" made of up-strokes and down-strokes — like a very jagged EKG line — that starts and ends at the same height and never dips below its starting level. The number of distinct mountain ranges you can draw with n up-strokes and n down-strokes is, once again, the n-th Catalan number. This is called a Dyck path, and it's a nice mental image for the whole family: any Catalan-counted object can be redrawn as one of these constrained up-down walks. The "never dip below the starting level" rule is a geometric translation of "never let closing parentheses outnumber opening ones."

The numbers themselves grow fast — but not quite as fast as you might expect. Since C(n) is roughly 4^n divided by n^1.5 times the square root of pi, the sequence grows almost as quickly as 4 raised to the n, but the polynomial factor in the denominator "tames" it just enough. By n = 20, the Catalan number is already over 6.5 billion; by n = 30, it's in the trillions. And yet Catalan numbers are always a strict fraction of the much larger binomial coefficient "2n choose n" — specifically 1/(n+1) of it — which is the elegant part: an enormous count of raw combinations divided down by exactly the right amount to eliminate every "crossing" or "unbalanced" case.

A geometric example you can draw yourself. Take a hexagon (6 sides) and draw every possible way to cut it into triangles using non-crossing diagonals. Try it on paper: you'll find exactly 14 distinct triangulations — the 4th Catalan number (since a hexagon has 6 = 4+2 sides). A square gives you 2 triangulations; a pentagon gives you 5. This was literally Euler's original question in 1751, and it's still one of the most visually intuitive ways to "see" a Catalan number.

Takeaways

• The Catalan numbers (1, 1, 2, 5, 14, 42, 132, 429, 1430...) count anything built from a "split into two independent, non-crossing smaller copies" pattern — parentheses, binary trees, polygon triangulations, non-crossing handshakes, and Dyck-path mountain ranges are all the same underlying structure in disguise.
• The formula C(n) = (2n)! / (n! × (n+1)!) — equivalently "2n choose n" divided by n+1 — turns an enormous raw combinatorial count into an exact count of only the "balanced" or "non-crossing" arrangements.
• The sequence has three independent discoverers across two centuries and two continents: Ming Antu in 1730s China, Euler and Segner in 1750s Europe, and Eugène Catalan in 1838 — a reminder that mathematical objects often get "discovered" more than once before anyone realizes it's the same idea wearing different clothes.
• The same math that counts ways to triangulate a hexagon also governs how compilers parse arithmetic, how RNA molecules fold, and how railway cars get shunted into order — a strong hint that "no crossings allowed" is one of nature's and computation's favorite constraints.
• Next time you see a set of matched parentheses, a binary decision tree, or a chord diagram, you're looking at a Catalan number in physical form.