The constant that counts what does not happen

Everything about $e$ so far in this ladder has been about change. It is the base whose curve is its own slope, the point where an area reaches one, the solution of an equation about rates, the thing a matrix does over time. Growth, in four costumes.

This rung is about the places it turns up where nothing grows at all. There is no rate of change in a shuffled pack of cards and none in the number 12!, and $e$ is in the middle of both.

A shuffle that misses everything #

Hand back $n$ hats to $n$ people at random. The chance that nobody gets their own is, for $n$ of any size at all, about 0.3679 — and it barely moves as $n$ grows. Four people and four hundred give nearly the same answer.

That constancy is the first surprise. Intuition suggests either that the chance should fall, because there are more ways to go wrong with more people, or rise, because each individual is less likely to meet their own hat. It does neither.

The count itself is settled by inclusion–exclusion: subtract the arrangements fixing at least one item, add back those fixing at least two, and so on. What comes out is

$$\frac{D_n}{n!} = 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots \pm \frac{1}{n!},$$

and there is the whole answer. That alternating sum of reciprocal factorials is the series for $e^x$ evaluated at $x = -1$, cut off after $n$ terms.

So the proportion is not approximately $1/e$ in some vague asymptotic sense. It is the first $n+1$ terms of the series for $1/e$, exactly, which is why the convergence is so fast — the error is the next term, at most $1/(n+1)!$, and by seven objects that is under a two-hundred-thousandth.

Why the exponential is there at all #

It is worth asking what a series about growth is doing in a counting problem, and the answer is short: it is not a series about growth. The series is a fact about the numbers $1/k!$, and the reciprocal factorials appear here because $k$ items can be chosen and permuted in $\binom{n}{k}(n-k)!$ ways, and that ratio to $n!$ is $1/k!$.

The exponential’s series is, in this reading, the generating function that counts labelled structures: dividing by $k!$ is exactly what is done when the order of a chosen set is irrelevant, and every counting problem in which pieces are chosen and then ignored produces reciprocal factorials. So $e$ turns up in counting for the same structural reason it turns up in growth — both are about $1/k!$ — and the two subjects meet in the series rather than in any shared idea about rates.

There is a matching probabilistic reading, which is the one worth carrying. Each person has probability $1/n$ of receiving their own hat, and the events are nearly independent. If they were exactly independent, the chance of all $n$ missing would be $(1 - 1/n)^n$, which is the compound-interest limit and tends to $1/e$. The events are not independent — the hats are handed out without replacement — and the remarkable thing is that the dependence cancels to a far higher order than it has any right to.

The distribution behind the constant #

There is a way of seeing the whole thing at once, and it explains the alternation as well as the limit.

Count how many people get their own hat. The expected number is exactly 1, whatever $n$ is: each person contributes $1/n$ and there are $n$ of them, and expectation adds up whether or not the events are independent. The variance is also exactly 1. And as $n$ grows, the whole distribution of that count settles onto the Poisson distribution with mean 1, whose probability of zero is $e^{-1}$.

So the derangement proportion is one entry of a limiting distribution, and the other entries are just as tidy: the chance that exactly one person gets their own hat also tends to $1/e$, the chance that exactly two do tends to $1/(2e)$, and in general exactly $k$ tends to $1/(k!\,e)$. Those are the Poisson probabilities, and they sum to 1 because the series for $e$ does.

That reframing turns the constant from a curiosity into an instance. The Poisson distribution is what a large number of rare, nearly-independent chances produces, and $e^{-\lambda}$ is in every one of its probabilities. Derangements are the case $\lambda = 1$, and the reason $\lambda = 1$ is that the expected number of fixed points is exactly one for every $n$ — a coincidence of the problem that makes the answer a clean $1/e$ rather than a clean $e^{-\lambda}$ for some less memorable $\lambda$.

The other place, where a factorial is nearly a power #

The second appearance is inside the factorial itself.

$n!$ grows faster than any exponential and is awkward to work with for exactly that reason: it has no closed form, and estimating it matters constantly, since it is the denominator of every probability in every counting problem. The estimate is

$$n! \approx \left(\frac{n}{e}\right)^n\sqrt{2\pi n},$$

which is Stirling’s approximation, and it contains both $e$ and $\pi$ in a statement about multiplying whole numbers together.

The $e$ has a clean origin and it is worth extracting, because the derivation explains the shape of the answer.

Take logarithms: $\ln n! = \ln 1 + \ln 2 + \cdots + \ln n$, a sum which is approximated by the area under $\ln x$ from 1 to $n$ — and that area is $n\ln n - n + 1$. Exponentiating,

$$n! \approx e^{n\ln n - n} = \frac{n^n}{e^n} = \left(\frac{n}{e}\right)^n.$$

The $e^{-n}$ is the $-n$ in the integral of the logarithm, nothing more. It comes from the fact that $\int \ln x\,dx = x\ln x - x$, and the $-x$ is there because differentiating $x\ln x$ produces an unwanted $+1$ that has to be cancelled. That is the whole of why $e$ appears in Stirling’s formula, and the area under a curve is again the mechanism.

The $\sqrt{2\pi n}$ is a different and harder story, which is where the bell curve comes in: it is the width of the peak of the integrand in an integral representation of the factorial, and the $\sqrt{2\pi}$ is the normalising constant of the normal distribution. Two constants, two mechanisms, one formula.

The smallest cases are worth having in front of the eye because they make the speed of the convergence concrete. One object: no derangements, proportion 0. Two: one out of two, proportion 0.5. Three: two out of six, 0.3333. Four: nine out of twenty-four, 0.375. Five: forty-four out of a hundred and twenty, 0.3667. The sequence is already oscillating tightly about 0.3679 by the time it can still be counted by hand, which is what an alternating series with factorial denominators does.

How good, and in what sense #

The word “approximation” is doing something specific here and it is easy to get backwards. The difference $n! - (n/e)^n\sqrt{2\pi n}$ grows without bound — at $n = 12$ it is over three million. What shrinks is the ratio, which is what the table measures, and it shrinks like $1 + 1/(12n)$.

That distinction is not pedantry. Stirling’s formula is used to estimate ratios of factorials — binomial coefficients, probabilities, entropies — and in a ratio the errors partly cancel. Used to estimate a factorial itself to within a fixed number, it is useless for any $n$ worth using it for.

The last column of the table above is the check that the error really behaves as claimed. $n$ times the relative excess sits at about 0.0836 for every row, and $1/12 = 0.0833$. The figure asserts that agreement rather than displaying it, which is what turns a table into evidence: a formula predicting $1/(12n)$ makes a claim about that column being flat, and a flat column is something a reader can see and a check can fail on.

A number nobody would guess #

It is worth dwelling on how unhelpful intuition is here, because the failure is instructive.

Asked for the chance that a random shuffle of a large pack leaves no card in its own place, most people offer either a number near zero or a number near one, on the reasoning that with fifty-two chances something is bound to match, or that each individual match is unlikely. Both reasonings are sound and both point at the boundary; the answer sits at 0.37, near neither.

The resolution is that the expected number of matches is exactly 1 — not large, not small — and a count with mean 1 is neither reliably zero nor reliably positive. The whole of the surprise is that the expected number does not depend on $n$: more people means more chances and each chance correspondingly rarer, and the two effects cancel exactly rather than approximately.

That exact cancellation is the fact worth carrying away, and it is the reason the answer is a constant rather than a function of $n$. Whenever a count’s mean is pinned at a fixed value by two effects trading off, a Poisson limit and a power of $e$ are what to expect.

What the two have in common #

Two appearances of $e$ in problems about counting, and it is fair to ask whether they have anything to do with each other beyond the letter.

They do, and the common object is the series. Both derivations pass through the same place: the derangement count is the truncated series for $e^{-1}$, and Stirling’s derivation goes through $e$ because the integral of a logarithm produces a linear term that exponentiates. Underneath both is the fact that $e^x$ is the function whose $n$-th derivative is itself, so its series has $1/n!$ in it — and $1/n!$ is what appears whenever an ordering is imposed and then discarded.

That is a genuine explanation rather than a coincidence, and it also predicts where else to look. Any counting problem in which $k$ things are selected and then their order forgotten will produce reciprocal factorials, and any such sum evaluated at $\pm 1$ will produce a power of $e$. The number of permutations with no cycle shorter than $k$; the distribution of the number of fixed points, which is Poisson with mean one; the probability that a random function has no small cycle — all of them are the same series read at different points.

Where else it turns up in counting #

Once the mechanism is named — reciprocal factorials, from choosing and then forgetting the order — the same constant becomes predictable in places that look unconnected.

The secretary problem. Interviewing candidates one at a time and hiring the first that beats everything seen so far, the best strategy is to reject the first fraction $1/e$ of them and then take the next record. The chance of getting the best candidate is also $1/e$. The $e$ arrives from an integral of $1/x$, which is the area from the second rung of this ladder, and the essay on when to stop looking works it out.

Records in a random sequence. The expected number of times a running maximum is beaten in $n$ draws is $1 + 1/2 + \cdots + 1/n$, which grows like $\ln n$ — the same logarithm, in a problem with no growth in it either.

Random permutations generally. The chance that a random permutation of $n$ things has no cycle of length one is $1/e$; the chance it has no cycle of length two tends to $e^{-1/2}$; and in general the number of $k$-cycles is Poisson with mean $1/k$. The whole cycle structure of a random permutation is governed by a family of these constants, and the harmonic sum turns up again as the expected number of cycles.

Three problems about arrangements, three appearances of the same constant, and in none of them is anything increasing.

What the picture cannot show #

The bars in the hero figure are exact counts, taken by enumerating every arrangement, and they stop at eight because $9!$ arrangements are more than a figure can enumerate honestly on a page and $12!$ is a wall. The claim being made is about all $n$, and the picture shows the first eight — which is exactly the situation the site’s standing warning about small cases is about. What rescues it here is that the closed form is exact and elementary, so the pattern is proved rather than extrapolated.

Stirling’s table has a subtler limit. It shows the ratio approaching 1 and cannot show that the sequence of corrections — $1/(12n)$, then $1/(288n^2)$, and so on — is a series that diverges. Adding more correction terms improves the estimate up to a point and then makes it worse without bound, which is characteristic of asymptotic expansions and is invisible in any table of the first few. A picture of a good approximation getting better says nothing about what happens if the improvement is pursued.

The ladder from here #

Rungs above: the Poisson distribution, of which the derangement count is one instance, and where $e^{-\lambda}$ appears for the same reason. Asymptotic series, and why an expansion can be divergent and still be the right tool. Stirling’s formula proved by Laplace’s method, where the $\sqrt{2\pi}$ is earned. The Gaussian integral, which is where the $\sqrt{\pi}$ comes from in the first place. And the exponential generating functions of which this essay’s series is the simplest example.

The lesson worth keeping #

The instinct on meeting $e$ in a problem about shuffling is to look for something growing, and there is nothing growing. That instinct comes from meeting the constant first as a rate of growth, which is a historical accident of how the subject is taught rather than a fact about the number.

What $e$ actually is, underneath every one of its appearances, is the sum of the reciprocal factorials. Growth is one consequence of that; counting is another; and neither is more fundamental. A constant met in one setting will keep turning up in others, and the reliable way to see why is to find the arithmetic identity that all its appearances pass through, rather than to look for the first setting hiding inside the later ones.