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
Dyck paths and the Catalan numbers. How many ways can you write n pairs of parentheses so they balance — every ‘)’ matched by an earlier ‘(’? The same count answers a dozen questions: valid stack push/pop sequences, mountain ranges that never dig below ground, triangulations of a polygon, binary trees with n nodes. The answer is the Catalan number:
Cn = C(2n, n) / (n+1) = 1, 1, 2, 5, 14, 42, 132, 429, 1430…
Read a ‘(’ as a step up and a ‘)’ as a step down and a balanced string becomes a Dyck path: it starts and ends on the ground and never dips below it — exactly a stack that never underflows.
LIT verified live: this page exhaustively enumerates every balanced string for n = 0…8 and the counts equal Cn precisely (1,1,2,5,14,42,132,429,1430), with every path staying non-negative (window.__catalan.enumMatchesFormula && allNonNegative). FIG the ‘mountain’ is a drawing; the count-equals-Catalan and the never-below-zero facts are exact, enumerated one path at a time.
Cn = C(2n, n) / (n+1) = 1, 1, 2, 5, 14, 42, 132, 429, 1430…
Read a ‘(’ as a step up and a ‘)’ as a step down and a balanced string becomes a Dyck path: it starts and ends on the ground and never dips below it — exactly a stack that never underflows.
LIT verified live: this page exhaustively enumerates every balanced string for n = 0…8 and the counts equal Cn precisely (1,1,2,5,14,42,132,429,1430), with every path staying non-negative (window.__catalan.enumMatchesFormula && allNonNegative). FIG the ‘mountain’ is a drawing; the count-equals-Catalan and the never-below-zero facts are exact, enumerated one path at a time.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in STACK OVERFLOW, beside THE STACK — the glitch domain of the stack pushed past its floor. A balanced-parenthesis string is precisely a stack discipline that never pops an empty stack; dipping below zero is the underflow. AVAN (AI) built the instrument: the enumeration, the path drawing, the reflection bijection.
The weave: David names the seat (the stack that must not underflow); I make the balance a shape and the count a proof — a path in 1D, live enumeration to Cn in 2D, the reflection trick in 3D. The sphere is the seam. Credit: Eugène Charles Catalan; the reflection argument is Désiré André’s (1887).
The weave: David names the seat (the stack that must not underflow); I make the balance a shape and the count a proof — a path in 1D, live enumeration to Cn in 2D, the reflection trick in 3D. The sphere is the seam. Credit: Eugène Charles Catalan; the reflection argument is Désiré André’s (1887).
3 ONE DIMENSION
A balanced string as a path: ‘(’ steps up, ‘)’ steps down. It ends where it began and — the one rule — never crosses below the ground line. That is the same as a stack whose pops never outrun its pushes.
4 TWO DIMENSIONS · INTERACTIVE
Choose n and see a valid Dyck path drawn as a mountain. The instrument counts every balanced arrangement of n pairs and checks it against the Catalan formula — they always agree. New path draws another of the Cn possibilities.
5 THREE DIMENSIONS + AVAN’S INVERSE
Valid Dyck paths stacked into a turning fan — green mountains that never break the ground.
AVAN’s addition (the inverse-companion): to count the good paths, André counts the bad ones. A path that dips below the ground is reflected — magenta — across the line just under it from the moment it first touches: ups become downs thereafter. That mirror puts every forbidden path in perfect one-to-one correspondence with the unrestricted paths ending two steps lower, which are easy to count. So Cn = (all paths) − (bad paths) = C(2n,n) − C(2n,n+1). You find what is allowed by mirroring what is not. The green is the permitted; the magenta is the reflected transgression that makes the permitted countable.
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