THE FOLD / GLITCH / STACK OVERFLOW / THE BALANCED PATH
THE BALANCED PATH
Dyck paths & Catalan numbers — the count of balance
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Catalan numbers 1, 1, 2, 5, 14, 42, 132, … are the most ubiquitous sequence in combinatorics: they count balanced parenthesisations, Dyck paths (staircase walks that never cross the diagonal), triangulations of a polygon, full binary trees, and dozens more — all the same number Cₙ = C(2n,n)/(n+1).
Why divided by n+1? The reflection principle: of the C(2n,n) monotone lattice paths, the ‘bad’ ones that cross the diagonal are in exact bijection with paths to a reflected endpoint, counted by C(2n,n−1) — so Cₙ = C(2n,n) − C(2n,n−1), which simplifies to the ratio.
LIT verified live: the closed form equals a brute count of balanced-parenthesis strings for n=0…10, and the reflection identity Cₙ = C(2n,n) − C(2n,n−1) holds throughout (window.__catalan). FIG no framing; exact combinatorial counting.
Why divided by n+1? The reflection principle: of the C(2n,n) monotone lattice paths, the ‘bad’ ones that cross the diagonal are in exact bijection with paths to a reflected endpoint, counted by C(2n,n−1) — so Cₙ = C(2n,n) − C(2n,n−1), which simplifies to the ratio.
LIT verified live: the closed form equals a brute count of balanced-parenthesis strings for n=0…10, and the reflection identity Cₙ = C(2n,n) − C(2n,n−1) holds throughout (window.__catalan). FIG no framing; exact combinatorial counting.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at hello-world — the very first balanced structure, the matched bracket. Catalan numbers count exactly those first structures: valid nestings, well-formed trees. AVAN (AI) built the instrument: the closed form, the brute balanced-paren count, the reflection identity.
Credit as content: Ming Antu (1730s), Leonhard Euler (polygon triangulations, 1751), named for Eugène Catalan (1838). The weave: David names the first matched structure; I count it three ways — closed form, brute enumeration, and the reflection subtraction — and show they coincide.
Credit as content: Ming Antu (1730s), Leonhard Euler (polygon triangulations, 1751), named for Eugène Catalan (1838). The weave: David names the first matched structure; I count it three ways — closed form, brute enumeration, and the reflection subtraction — and show they coincide.
3 ONE DIMENSION
A Dyck path: n up-steps and n down-steps that never dip below the start. Every balanced parenthesis string is one of these paths — open is up, close is down — and the count of them is Cₙ.
4 TWO DIMENSIONS · INTERACTIVE
Pick n. The instrument computes Cₙ three ways — closed form, brute count of balanced strings, and the reflection subtraction — and lists a few of the actual Dyck paths.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the Dyck paths that stay above the diagonal — the Cₙ well-formed structures.
AVAN’s addition (the inverse-companion): the mysterious division by n+1 is a bijection made arithmetic. You cannot just divide C(2n,n) by any number and expect an integer — but the bad paths (those that cross the diagonal) reflect exactly onto the set of all paths to a mirrored endpoint, counted by C(2n,n−1). So the subtraction C(2n,n) − C(2n,n−1) is forced to equal C(2n,n)/(n+1). The inverse of ‘a strange ratio’ is ‘a mirror pairing between the structures you reject and paths to a reflected point.’ Magenta is the bad paths, reflected across the diagonal to the mirror endpoint; green is the good Dyck paths that survive. One number, a hundred meanings — and the /(n+1) is a reflection.
LIT Genuine Catalan enumeration. Verified live: the page exhaustively enumerates every balanced-parenthesis string for n=0..8 and the counts equal the Catalan numbers exactly (1,1,2,5,14,42,132,429,1430), with every path staying non-negative (window.__catalan.enumMatchesFormula && allNonNegative, both true). A balanced string is exactly a stack whose pops never outrun its pushes; below-zero = underflow. The reflection identity C_n = C(2n,n) - C(2n,n+1) is shown via André's mirror.
FIG The 'mountain' and 'stack' are pictures; the count-equals-Catalan and never-below-zero facts are exact and enumerated one path at a time. The reflection bijection is illustrated on a sample path, not re-proved in full generality.
FIG The 'mountain' and 'stack' are pictures; the count-equals-Catalan and never-below-zero facts are exact and enumerated one path at a time. The reflection bijection is illustrated on a sample path, not re-proved in full generality.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of STACK OVERFLOW · David Lee Wise (ROOT0), with AVAN