THE FOLD / SPAWN / GENESIS BLOCK / THE CAYLEY FORMULA
THE CAYLEY FORMULA
how many labeled trees on n dots
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Cayley’s formula is one of the most elegant counting results in all of mathematics: the number of distinct labeled trees on n vertices is exactly nn-2. Three vertices give 3 trees; four give 16; ten give a hundred million. The cleanest proof is a bijection: Prüfer’s encoding turns every labeled tree into a unique sequence of n-2 numbers from {1,…,n}, and every such sequence decodes back to a unique tree. Since there are nn-2 possible sequences, there are exactly that many trees. The encoding repeatedly removes the smallest leaf and records its neighbour; the decoding reverses it.
LIT verified live: an exhaustive brute-force count of labeled trees for n = 3, 4, 5, 6 equals nn-2 exactly, and Prüfer’s map is confirmed a bijection — all nn-2 sequences decode to distinct valid trees and encoding inverts decoding (window.__cayley). FIG no framing; the brute tree count, the Prüfer encode/decode, and the bijection check all run in-browser.
LIT verified live: an exhaustive brute-force count of labeled trees for n = 3, 4, 5, 6 equals nn-2 exactly, and Prüfer’s map is confirmed a bijection — all nn-2 sequences decode to distinct valid trees and encoding inverts decoding (window.__cayley). FIG no framing; the brute tree count, the Prüfer encode/decode, and the bijection check all run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at genesis-block — the origin from which whole forests spring: from n labeled points, exactly nn-2 distinct trees can grow, each a different lineage from the same seed set. AVAN (AI) built the instrument: the exhaustive tree count, the Prüfer encoding and decoding, and the bijection verification.
Credit as content: Arthur Cayley (1889); the bijective proof by Heinz Prüfer (1918). The weave: David names the genesis block; I confirm the tree count is nn-2 and Prüfer’s map is a perfect bijection.
Credit as content: Arthur Cayley (1889); the bijective proof by Heinz Prüfer (1918). The weave: David names the genesis block; I confirm the tree count is nn-2 and Prüfer’s map is a perfect bijection.
3 ONE DIMENSION
A labeled tree and its Prüfer sequence: repeatedly remove the smallest leaf, record its neighbour, until two vertices remain.
4 TWO DIMENSIONS · INTERACTIVE
The brute tree count vs n^(n-2), and the Prüfer round-trip; cycle a Prüfer sequence to see its decoded tree.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a labeled tree grown from the n vertices.
AVAN’s addition (the inverse-companion): don’t draw the tree — write its code. The inverse of ‘a labeled tree’ is ‘its Prüfer sequence of n-2 numbers’, and because that map is a bijection, counting sequences counts trees: nn-2. Magenta is the Prüfer sequence; green is the tree it encodes. A forest counted by its addresses.
LIT Genuine Cayley's formula (Arthur Cayley 1889; bijective proof by Heinz Prüfer 1918). Verified live: exhaustive brute-force count of labeled trees for n=3,4,5,6 equals n^(n-2) (3,16,125,1296), and the Prüfer map is a bijection — all 125 sequences for n=5 decode to distinct valid trees and encode∘decode is the identity (window.__cayley.formulaOk, .bijOk).
FIG No framing; the brute tree count, the Prüfer encode/decode, and the bijection check all run in-browser. The AVAN inverse is honest — instead of drawing the tree, write its code: its Prüfer sequence of n-2 numbers, and because that map is a bijection, counting sequences counts trees (n^(n-2)). Magenta is the Prüfer sequence; green is the tree it encodes. A forest counted by its addresses.
FIG No framing; the brute tree count, the Prüfer encode/decode, and the bijection check all run in-browser. The AVAN inverse is honest — instead of drawing the tree, write its code: its Prüfer sequence of n-2 numbers, and because that map is a bijection, counting sequences counts trees (n^(n-2)). Magenta is the Prüfer sequence; green is the tree it encodes. A forest counted by its addresses.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of GENESIS BLOCK · David Lee Wise (ROOT0), with AVAN