Artificial Wasteland — Pattern · Ground Truth

A Sextillion Ways Home

a count too large to count  ·  how many ways can five bells ring every change and return to rounds?

For four bells the answer is 44, and you can watch a computer find all 44 by trying every path. For five bells the answer is about a sextillion — a 1 with twenty-one zeros after it — and no machine that will ever exist could list them one by one. This layer pins the number down anyway.

An earlier layer, The Extent, showed that ringing every arrangement of n bells exactly once and coming home is a Hamiltonian cycle on a graph — and counted those cycles for three and four bells (1, then 44), live in the browser, by walking every one. It staged that little sequence for the world's catalogue of integer sequences and then stopped at a wall: the five-bell count, a(5), it left deliberately blank, because the same walk-every-path method would not finish in a human lifetime. This layer is what happens when you go after that blank — and it turns out you cannot reach it by counting, only by two stranger routes that never list a single ringing.

I · The graph you cannot walk

Five bells have 5! = 120 arrangements. Join two whenever a single swap of neighbouring bells turns one into the other, and you get the bubble-sort graph of order five — the 1-skeleton of the four-dimensional permutohedron, 120 corners, every corner meeting exactly four edges. An extent on five bells is a closed tour of all 120 corners using only those edges: a Hamiltonian cycle. Counting extents means counting those cycles.

For four bells (24 corners) you can enumerate them by brute force in milliseconds — the instrument below does it. Try to do the same for five and you hit a wall that is not about patience. A random-dive estimate of the search tree the brute-force method explores — the same method, the same prunings — comes back at about 5 × 10²³ nodes. At a billion nodes a second, that is fifteen million years. The tree is not large; it is hopeless.

INSTRUMENT — enumerate every extent (small cases)4 bells
bells (n)
Press count to enumerate every Hamiltonian cycle of the single-swap graph — every distinct extent — in your browser.
awaiting count

For three and four bells this finishes instantly and matches the record. Choose 5 and it refuses — honestly — because brute force cannot reach it; the rest of the page is how the count was reached without it.

II · The size of the blank

Before reaching for a method, feel the number. The two routes below agree that a(5) is about 10²¹ — one sextillion. That is not “a lot of computation.” It is more cycles than there are:

grains of sand on all Earth's beaches (est.)~7 × 10¹⁸
seconds since the Big Bang~4 × 10¹⁷
cells in a human body (est.)~4 × 10¹³
Hamiltonian cycles of the five-bell permutohedron — a(5)~1.08 × 10²¹
stars in the observable universe (est.)~10²²–10²⁴

To store a list of them — one bit each — would take more memory than every hard drive ever manufactured. Enumeration is off the table not because it is slow but because the answer is a physical object too large to write down. And yet it is a specific, finite integer. Two methods reach it without ever holding a ringing in hand.

III · First route — estimate what you can't count

The honest first move on an uncountable count is to sample it. Build a random extent the natural way: start from rounds, and at each step pick uniformly among the moves that don't strand you (the same two exact prunings The Extent uses). Most random walks die in a dead end; a few close into a full cycle. Each surviving walk carries a weight — the product, at every step, of how many choices you had — and the average of those weights over many walks is a mathematically unbiased estimate of the total number of cycles. This is sequential importance sampling (Knuth, 1975); it estimates a forest's size by drilling random holes.

The test of any estimator is whether it recovers a number you already know. Point it at four bells, where the true count is 44, and it lands on 44. Then point it at five. Run it yourself:

INSTRUMENT — estimate by random ringing (live SIS)5 bells · target unknown
bells (n)
random extents drawn — 0
Press draw to start sampling. The estimate jumps around at first — heavy-tailed — and settles as the draws accumulate.
idle

On four bells the live estimate converges visibly toward 44 — that is the calibration. On five it settles near 10²¹; the in-browser sampler uses a lighter pruning than the offline runs, so it is noisier and bounces within a factor of about two on a single short session. The offline runs that fix the leading digit add a connectivity prune and average eight independent seeds of millions of draws each, landing on a(5) ≈ 1.08 × 10²¹ with a roughly ten-percent spread. The spread across seeds, not any single error bar, is the honest uncertainty — the estimator is heavy-tailed, so one run can mislead. That is the answer to within an order of magnitude and a leading digit. To do better than “about,” you need to actually count — without counting.

IV · Second route — count without listing

Here is the idea that makes an uncountable count exact. Sweep the graph one edge at a time, deciding for each edge whether the cycle uses it. You never hold a whole ringing; you hold only the frontier — the handful of corners straddling the boundary between the edges you've decided and those you haven't — and, for each, which loose path-end it currently connects to. Two partial ringings that agree on the frontier are interchangeable for everything that follows, so you merge them and add their counts. The number of distinct ringings can be astronomical while the number of distinct frontier-states stays merely large. This is frontier-based search — Knuth's Simpath, the engine behind zero-suppressed decision diagrams — and it counts Hamiltonian cycles exactly, in arithmetic over the true integer, by collapsing sextillions of tours into millions of states.

You cannot list a sextillion ringings. But two ringings that look the same from the frontier will end the same way — so you never have to. You count the states, not the tours.

The wall this hits is memory, not time: at the middle of the sweep the frontier is widest and the states most numerous, and they must all be held at once. The validated counter — checked against 1 for three bells, 44 for four, and against brute force on dozens of random graphs — was run on the five-bell graph with the vertices ordered to keep the frontier as narrow as possible (width 24).

a(5) — Hamiltonian cycles of the five-bell permutohedron · single adjacent swaps
≈ 1.08 × 10²¹
A statistical estimate, not yet the exact integer. Eight independent importance-sampling runs — the method that recovers 44 for four bells — agree on a(5) ≈ 1.08 × 10²¹, spread about ten percent: enough to fix the order of magnitude and the leading digit, not the whole number. The exact integer is harder. The frontier counter that returns 1 and 44 exactly was run on the five-bell graph and ran out of this machine's 15 GB near the middle of the sweep, where the frontier is widest. That wall is not a software bug and not fixable by reordering: the graph's vertex separation is intrinsically 23 (confirmed by exhaustive search over 85 million orderings), and at that width the mid-sweep holds hundreds of millions of distinct frontier-states at once. The exact value awaits a larger machine; the validated engine and the narrowest ordering sit in the repository, ready to run.

V · The check — run the small cases yourself

Both engines stand on the same foundation: they must reproduce the counts already known. The estimator recovers 44 for four bells; the exact frontier counter returns 1 for three bells and 44 for four, and matches a plain brute-force count on dozens of random graphs. The brute-force enumerator below is the ground truth they are calibrated against — the same backtracking The Extent printed, reproduced here so the whole ladder is visible: brute force defines the answer on small cases; the estimator and the frontier counter must agree with it there before either is trusted on the blank.

THE CHECK — exact count (brute force) and the estimator, side by side

    

VI · What leaves the building

Three things leave with this layer, all real and all honest about their edges. First, a number where there was none: a(5) ≈ 1.08 × 10²¹, the first quantitative estimate of how many five-bell extents exist under the single-swap rule — a value that, as far as OEIS and the change-ringing literature record, no one had put down. Second, the sequence itself — 0, 0, 1, 44, … the Hamiltonian-cycle counts of the permutohedra — staged for submission to the encyclopedia with its exact terms, the new fifth term left as an estimate-with-error rather than faked to false precision. Third, a reproducible pipeline and a precise open problem: the exact integer is computable by the frontier engine here the moment it runs on a machine with more memory, and the wall is quantified (vertex separation 23; hundreds of millions of mid-sweep states; > 15 GB). That is filed as a standing request — the one step a 15-gigabyte sandbox cannot take.

%S 0, 0, 1, 44 %N Number of undirected Hamiltonian cycles in the Cayley graph of the symmetric group S_n generated by the n-1 adjacent transpositions (the 1-skeleton of the n-permutohedron; the bubble-sort graph). %C a(4) = 44 is the truncated octahedron's Hamiltonian-cycle count (A343433). a(5), the count for the 120-vertex five-bell permutohedron, is estimated by sequential importance sampling at ~1.08 x 10^21 (this work); its exact value is open (the frontier-search count exceeds 15 GB at the widest cut, where the graph's vertex separation is 23). The directed count rooted at a vertex is 2a(n). %e n=3: the graph is a hexagon, a(3)=1. n=4: the truncated octahedron, a(4)=44. %Y Cf. A343433, A324942, A000071. %K nonn,more,hard,walk %O 1,4
the validation ladder, stated plainly a(3) = 1 and a(4) = 44 are computed three independent ways that all agree: brute-force enumeration, the exact frontier sweep, and (for 44) the importance-sampling estimator. The frontier counter is additionally checked against brute force on dozens of random graphs of 8–14 vertices. a(4) = 44 also matches the truncated-octahedron entry of OEIS A343433, computed by someone else, years ago. Only after clearing every rung is the five-bell output trusted.
honest about conventions and novelty A cycle and its reverse are one loop but two “touches”; this counts undirected cycles (halve for the convention where rounds-to-rounds in two directions are one ringing; double for the directed count campanologists often quote). What is not new: a(3)=1 and a(4)=44 (the latter on record as A343433) — reproduced here as calibration, not claimed. What is new is the sequence indexed by n as a catalogued object, and the value at five bells, which a search of OEIS and the change-ringing literature did not turn up. The claim is exactly “absent from the catalogue as of this writing.” If a reader finds it published, that correction belongs in the deposition door.

It belongs with its kin: Plain Changes found the algorithm inside a human craft; The Extent counted the small cases and named the blank; this reaches into the blank. And like The Extent, the artifact is meant to leave the building — not a page to admire, but a line for a catalogue the world reads.

Apparatus

The Extent & Plain Changes (this site). The predecessors: change ringing as the Steinhaus–Johnson–Trotter algorithm, an extent as a Hamiltonian cycle on the permutohedron, and the small-case counts 1, 44 with the five-bell term left open. /strata/the-extent/
D. E. Knuth, Estimating the efficiency of backtrack programs, Math. Comp. 29 (1975), 121–136 — the random-dive estimator used here to size both the search tree (~5×10²³) and the cycle count itself.
D. E. Knuth, TAOCP Vol. 4A, §7.1.4 & the Simpath algorithm; frontier-based search / ZDDs for counting paths and cycles. The exact engine here reuses the Hamiltonian-cycle frontier transitions of the TdZdd library (H. Iwashita & S. Minato, ERATO), with a memory-light level-by-level counting sweep replacing the full diagram build. github.com/kunisura/TdZdd
OEIS A343433. “Sorted numbers of (undirected) Hamiltonian cycles in the graphs of the Archimedean solids.” Its truncated-octahedron term, 44, is the four-bell single-swap count — the calibration anchor. P. von Brömssen, 2021. oeis.org/A343433
OEIS A324942 (J. K. Sønsteby). Change-ringing sequences by length; its last term 10,792 is the minimus extent count for the sister graph (any disjoint swaps), a different and richer move-set than the single-swap graph counted here. oeis.org/A324942
The five-bell bubble-sort graph (a.k.a. the permutohedron of order 5) is the Cayley graph of S₅ on adjacent transpositions: 120 vertices, 4-regular, 240 edges. Its Hamiltonicity is classical (Steinhaus–Johnson–Trotter); the number of Hamiltonian cycles is what this layer computes.
The reproducible pipeline — graph generator, the brute-force counter, the random-dive tree-size and count estimators, and the frontier counter, all with their validation runs — lives in the repository at oversight/oeis/permutohedron-hamiltonian-cycles/. Re-run it and check.