THE FOLD / LOOT / THE BOUNTY / THE FUSS-CATALAN
THE FUSS-CATALAN
counting m-ary trees
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Fuss–Catalan numbers generalize the Catalan numbers from binary trees to m-ary trees. Where the Catalan number Cn counts full binary trees with n internal nodes (each with 2 children), the Fuss–Catalan number counts full m-ary trees with n internal nodes (each with m children) — and it has the same style of closed form: (1/((m-1)n+1))·C(mn, n). For m = 2 it is exactly Catalan (1, 2, 5, 14, 42, …); for m = 3 it counts ternary trees (1, 3, 12, 55, 273, …). It answers ‘how many ways to fully parenthesize with an m-ary operation’ and appears across lattice-path and polygon-dissection counting.
LIT verified live (exact BigInt): for m = 2, 3, 4 and n up to 6, a brute recursive count of full m-ary trees with n internal nodes equals the closed form (1/((m-1)n+1))C(mn, n) exactly — C₂(4) = 14 (Catalan), C₃(4) = 55, C₄(4) = 140 (window.__fusscatalan). FIG no framing; the recursive tree count and the binomial formula both run in-browser with arbitrary-precision integers.
LIT verified live (exact BigInt): for m = 2, 3, 4 and n up to 6, a brute recursive count of full m-ary trees with n internal nodes equals the closed form (1/((m-1)n+1))C(mn, n) exactly — C₂(4) = 14 (Catalan), C₃(4) = 55, C₄(4) = 140 (window.__fusscatalan). FIG no framing; the recursive tree count and the binomial formula both run in-browser with arbitrary-precision integers.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-bounty — a vast count of tree shapes, the m-ary bounty that Catalan’s binary count is only the first slice of. AVAN (AI) built the instrument: the recursive m-ary tree count (a convolution), the closed-form binomial, and their exact BigInt agreement.
Credit as content: Nicolaus Fuss (1791), a student of Euler; the Catalan case by Eugène Catalan. The weave: David names the bounty; I confirm the recursive m-ary tree count equals the Fuss–Catalan formula.
Credit as content: Nicolaus Fuss (1791), a student of Euler; the Catalan case by Eugène Catalan. The weave: David names the bounty; I confirm the recursive m-ary tree count equals the Fuss–Catalan formula.
3 ONE DIMENSION
A full m-ary tree with n internal nodes; the Fuss–Catalan number counts all such shapes.
4 TWO DIMENSIONS · INTERACTIVE
Cycle m and n; the recursive tree count is compared to the closed form (1/((m-1)n+1))C(mn,n).
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the Fuss–Catalan count of full m-ary trees.
AVAN’s addition (the inverse-companion): don’t enumerate the trees — convolve the sub-counts. The inverse of ‘count full m-ary trees with n internal nodes’ is ‘the recurrence T(n) = ∑ over the m subtree sizes summing to n-1’, which closes to (1/((m-1)n+1))C(mn,n). Magenta are the m branching subtrees; green is the total count they build. Binary Catalan, extended to m ways.
LIT Genuine Fuss–Catalan numbers (Nicolaus Fuss, 1791, a student of Euler; Catalan case by Eugène Catalan). Verified live with exact BigInt: for m=2..4 and n=0..6, a brute recursive count of full m-ary trees with n internal nodes equals (1/((m−1)n+1))C(mn,n) exactly — C₂(4)=14, C₃(4)=55, C₄(4)=140 (window.__fusscatalan.ok, .c2, .c3, .c4).
FIG No framing; the recursive m-ary tree count and the binomial formula both run in-browser with arbitrary-precision integers. The AVAN inverse is honest — instead of enumerating the trees, convolve the sub-counts: the recurrence T(n)=Σ over the m subtree sizes summing to n−1 closes to (1/((m−1)n+1))C(mn,n). Magenta are the m branching subtrees; green is the total count they build. Binary Catalan, extended to m ways.
FIG No framing; the recursive m-ary tree count and the binomial formula both run in-browser with arbitrary-precision integers. The AVAN inverse is honest — instead of enumerating the trees, convolve the sub-counts: the recurrence T(n)=Σ over the m subtree sizes summing to n−1 closes to (1/((m−1)n+1))C(mn,n). Magenta are the m branching subtrees; green is the total count they build. Binary Catalan, extended to m ways.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE BOUNTY · David Lee Wise (ROOT0), with AVAN