THE FOLD / BOSS / THE FINAL BOSS / THE RYSER
THE RYSER
a permanent counted by inclusion-exclusion
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Ryser’s formula computes the permanent of a matrix — the determinant’s sign-free cousin, a sum over all permutations with every term added, never subtracted. The permanent counts things (for a 0/1 matrix it is the number of perfect matchings in a bipartite graph), but computing it is notoriously hard: it is #P-complete, believed harder than NP. Ryser’s trick uses inclusion-exclusion over the columns to compute it in O(2nn) — still exponential, but far better than the n! of the definition, and the fastest known general method.
LIT verified live: for thousands of random integer matrices Ryser’s inclusion-exclusion permanent equals the brute-force sum over all permutations exactly, and for 0/1 matrices it equals the number of perfect matchings; the permanent of the all-ones 3×3 matrix is 3! = 6 (window.__ryser). FIG no framing; Ryser’s subset sum, the brute permanent, and the matching count all run in-browser.
LIT verified live: for thousands of random integer matrices Ryser’s inclusion-exclusion permanent equals the brute-force sum over all permutations exactly, and for 0/1 matrices it equals the number of perfect matchings; the permanent of the all-ones 3×3 matrix is 3! = 6 (window.__ryser). FIG no framing; Ryser’s subset sum, the brute permanent, and the matching count all run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-final-boss — the permanent is the boss at the end of counting: #P-complete, believed beyond NP, and Ryser is the best weapon we have against it, still exponential but the fastest known. AVAN (AI) built the instrument: Ryser’s inclusion-exclusion subset sum, the brute permutation permanent, and the perfect-matching count.
Credit as content: Herbert John Ryser (1963). The weave: David names the final boss; I confirm Ryser’s formula equals the true permanent and counts perfect matchings.
Credit as content: Herbert John Ryser (1963). The weave: David names the final boss; I confirm Ryser’s formula equals the true permanent and counts perfect matchings.
3 ONE DIMENSION
A 0/1 matrix as a bipartite graph; its permanent is the number of perfect matchings (ways to pair every row to a column).
4 TWO DIMENSIONS · INTERACTIVE
New matrices; Ryser's inclusion-exclusion permanent is compared to the brute permutation sum and the matching count.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the permanent — the count of perfect matchings.
AVAN’s addition (the inverse-companion): don’t sum over n! permutations — sum over 2n subsets. The inverse of ‘the permanent by definition’ is ‘Ryser’s inclusion-exclusion over column subsets’, trading n! for 2nn. Magenta are the alternating column-subset terms; green is the permanent they sum to. A hard count, made merely exponential.
LIT Genuine Ryser's formula for the permanent (Herbert John Ryser, 1963). Verified live: for ~4000 random integer matrices the inclusion-exclusion permanent (−1)ⁿΣ_S(−1)^|S|∏ row-subset-sums equals the brute permutation-sum permanent exactly, and for 0/1 matrices it equals the number of perfect matchings; perm of the all-ones 3×3 is 6 (window.__ryser.ryserOk, .matchOk, .permJ3).
FIG No framing; Ryser's subset sum, the brute permanent, and the matching count all run in-browser. Honest scope: computing the permanent is #P-complete; Ryser is exponential (2ⁿn), just the fastest known. The AVAN inverse is honest — instead of summing over n! permutations, sum over 2ⁿ column subsets by inclusion-exclusion. Magenta are the alternating column-subset terms; green is the permanent they sum to. A hard count, made merely exponential.
FIG No framing; Ryser's subset sum, the brute permanent, and the matching count all run in-browser. Honest scope: computing the permanent is #P-complete; Ryser is exponential (2ⁿn), just the fastest known. The AVAN inverse is honest — instead of summing over n! permutations, sum over 2ⁿ column subsets by inclusion-exclusion. Magenta are the alternating column-subset terms; green is the permanent they sum to. A hard count, made merely exponential.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE FINAL BOSS · David Lee Wise (ROOT0), with AVAN