Factorial explosion

Why is a shuffled deck of cards almost certainly in an order no deck has ever held before?

Shuffle a deck properly and the claim usually made is that the resulting order has never occurred before in the history of card playing. That sounds like the sort of thing people say for effect. Decks are small, fifty-two objects, and humans have been shuffling them for centuries. So is the claim rhetoric, or is there something about counting arrangements that we are systematically bad at estimating?

Count carefully rather than guess. To lay out n distinct objects in a row: n choices for the first position, n-1 for the second, n-2 for the third, and so on. Multiply them and you have n factorial, written n!. Nothing subtle has happened yet — it is just a product.

The subtlety is in how the product behaves. Ask yourself what happens when you add one more object to a set of n. Every arrangement you already had can now be extended in n+1 ways, so the count is multiplied by n+1. Not increased by a fixed amount, not doubled — multiplied by a factor that itself keeps growing.

Watch the numbers. 5! is 120, small enough to write out. 10! is 3,628,800 — already beyond hand enumeration. 20! is 2,432,902,008,176,640,000, about 2.43 billion billion. And 60! is roughly 8.3 x 10^81, which is larger than the commonly cited estimate for the number of atoms in the observable universe, around 10^80. Sixty objects. You could hold them.

Now the deck. 52! is about 8.07 x 10^67 — a sixty-eight digit number. Suppose, generously, that every one of ten billion people had shuffled a deck once per second since the universe began; that is under 10^28 shuffles. Against 10^67 possible orders, the fraction explored is so far below one that any given fair shuffle is, with overwhelming probability, unprecedented. The claim was not rhetoric.

Here is the distinction worth holding onto, because it is usually blurred. Exponential growth — 2^n, say — multiplies by a constant at each step. Factorial growth multiplies by a growing factor. At n = 20, 2^20 is about a million while 20! is about 2.4 million million million. Factorial eventually outruns any fixed exponential, and outruns it very quickly. When someone calls a factorial algorithm "exponential", they are being kind to it.

Why does this matter beyond card tricks? Consider the travelling salesman problem: visit n cities once each, return home, minimise total distance. Checking every tour means examining (n-1)!/2 of them. For twenty cities that is roughly 6 x 10^16 tours — and if you managed a billion tours per second, it would still take about two years. Twenty-five cities, and you are past the age of the universe.

So what should we conclude? Not that the problem is unsolvable, but that enumeration is not the route. Held and Karp's dynamic-programming method solves the same problem in time proportional to n^2 x 2^n, which is still exponential and still hopeless at scale — but it moves the wall from around twenty cities to around thirty, purely by refusing to look at each tour separately. Beyond that, practitioners use heuristics: nearest-neighbour construction, local improvement moves like 2-opt and Lin-Kernighan, branch-and-bound with good lower bounds. Modern solvers do prove optimality for surprisingly large instances — tens of thousands of cities — by pruning, not by counting.

Does that make heuristics a confession of laziness? Reverse the question: what would the alternative be? Against 10^67, no amount of hardware, patience, or funding closes the gap; doubling your computer buys you one more city. A method that gets within two percent of optimal in seconds is not a compromise on rigour. It is the only thing that is physically available.

Three refinements connect the steps above.

First, the deck argument depends on the shuffle actually being fair. Seven riffle shuffles is the well-known figure from Bayer and Diaconis for getting close to uniform; a casual two or three leaves substantial structure, and a fresh deck opened and cut a couple of times may well repeat an order that has occurred before. The mathematics of 52! is not in doubt — the assumption about the shuffle sometimes is.

Second, an enormous space does not by itself make a problem hard. Sorting n items also has n! possible orderings, and we sort millions of items routinely, because sorting has structure that lets us discard almost the entire space without looking at it. Difficulty comes from the absence of exploitable structure, not from the size of the count.

Third, "heuristics are necessary" is not the same as "optimality is unreachable". For the travelling salesman problem specifically, exact solvers have proved optimal tours for instances with tens of thousands of cities. What they never do is enumerate. The necessity is about the method, not about the standard of proof.

• Why some enormous search spaces (sorting, shortest paths) collapse under structure while others do not.
• What "NP-hard" actually claims about the travelling salesman problem, and what it does not.

Every term the collection defines is gathered in the glossary.