Coins hidden in the roots

A descent of a permutation is a place where it steps down. The permutation 3 1 4 2 5 has descents after the 3 and after the 4, so it has two. Counting the 120 permutations of five things by their number of descents gives 1, 26, 66, 26, 1, and putting those counts on the powers of a second variable gives a polynomial,

$$A_5(x) = 1 + 26x + 66x^2 + 26x^3 + x^4 ,$$

one of the Eulerian polynomials, named after Euler, who met them summing series long before anyone counted descents.

The inversion count has a product formula: $1 \cdot (1+q)(1+q+q^2)\cdots$, one factor for each item inserted, and the product says the inversion count is a sum of independent pieces. The descent count has no such formula. Inserting the items one at a time changes the descent count by zero or one, but the chance of each depends on how many descents are already there, so the pieces are not independent and the polynomial does not factor over the integers.

It does factor over the reals, and the factors are the whole point of this essay. Every root of $A_n(x)$ is real and negative. That single fact makes the descent count a sum of independent coin tosses — coins that appear nowhere in the definition — and from that follow its bell shape, its variance, and a family of inequalities its coefficients must satisfy.

Why the descent polynomial does not factor #

It helps to see where the Eulerian numbers come from, because the reason there is no product formula is visible in the recurrence. Take a permutation of $n - 1$ things with $k$ descents and insert the largest item, $n$, into one of its $n$ gaps. If $n$ goes at the very end, or into the middle of an existing descent — between a larger and a smaller neighbour — the number of descents stays $k$: at the end it creates nothing, and inside a descent it replaces one step down with a step up followed by a step down. There are $k + 1$ such places. In any of the other $n - k - 1$ places, including the very front, it creates one new descent. So

$$A(n, k) = (k + 1)\, A(n - 1, k) + (n - k)\, A(n - 1, k - 1),$$

which is the rule the figures use, checked for small $n$ against a direct count of descents in every permutation.

Compare the inversions. Inserting the $n$-th item among $n$ positions adds anywhere from $0$ to $n - 1$ inversions, one each, whatever the permutation was. The number added does not depend on the past, which is why the generating polynomial picks up a factor $1 + q + \cdots + q^{n-1}$ at each step. For descents the chance of adding one is $(n - k - 1)/n$, which depends on $k$, the number of descents already there. The steps are not independent, the polynomial does not factor step by step, and no rearrangement of the construction has been found that makes it do so.

That dependence is also why the result below is surprising. A process whose steps are not independent produces a total whose distribution is, exactly, that of a sum of independent steps — just not the steps of the process.

Where the polynomial vanishes #

A polynomial with whole-number coefficients can be tested for real roots exactly, without any rounding. Its sign at a rational point is a whole-number computation, and a change of sign between two points proves a root between them.

For $n = 10$ the polynomial has degree nine, and a scan of the negative axis on a fine logarithmic grid finds nine sign changes. Nine sign changes for a polynomial of degree nine account for every root, so all nine are real and negative, and bisection pins each one down. They are spread over many orders of magnitude, from about $-0.001$ to about $-1000$, and they pair off as $r$ and $1/r$: the coefficients read the same forwards and backwards, $A(n,k) = A(n,n-1-k)$, and a polynomial with that symmetry has a root at $1/r$ whenever it has one at $r$.

The pattern persists at twenty, and it is a theorem for every $n$, proved by Frobenius in 1910. The usual modern proof is by interlacing: the roots of $A_{n+1}$ fall one in each gap between consecutive roots of $A_n$, which follows from a recurrence relating each polynomial to the previous one and its derivative. The figures do not prove the theorem; they check it at two sizes, exactly, by counting sign changes — the same idea that counts real roots from a chain of remainders.

A root is a coin #

Here is why the roots matter. Write the polynomial in terms of its roots $r_1, \ldots, r_d$, all negative, and divide by its value at $x = 1$, which is the total count $n!$:

$$\frac{A_n(x)}{A_n(1)} = \prod_{i=1}^{d} \frac{x - r_i}{1 - r_i} = \prod_{i=1}^{d} \bigl( q_i + p_i x \bigr), \qquad p_i = \frac{1}{1 - r_i}, \quad q_i = 1 - p_i .$$

Each factor $q_i + p_i x$ is the generating function of a single coin that lands heads, contributing one, with chance $p_i$, and tails, contributing zero, with chance $q_i$. Because $r_i$ is negative, $p_i$ lies strictly between zero and one: a genuine probability. And a product of generating functions is the generating function of a sum of independent quantities — the rule the first of these essays started from. So the left-hand side, which is the distribution of the number of descents of a random permutation, is the distribution of the number of heads among $d$ independent coins with chances $p_1, \ldots, p_d$.

For $n = 10$ the nine coins have chances ranging from nearly one to nearly zero, symmetric about a half: the root $r$ and the root $1/r$ give chances $p$ and $1 - p$. Toss all nine and count heads, and the distribution of the count matches the distribution of descents among the 3,628,800 permutations of ten to nine decimal places — the difference is floating-point rounding in the roots, not a discrepancy in the claim.

The mean and variance come out of the coins directly. The mean of a sum of coins is the sum of their chances, and the variance is the sum of $p_i q_i$. For descents those sums are $(n-1)/2$ and $(n+1)/12$, which the figure checks at $n = 10$: mean $4.5$, variance $0.917$. Neither formula is hard to derive by other means, but here they fall out of nine numbers read off the roots.

What the coins do not do is describe any procedure. There is no known way to generate a random permutation by tossing these nine coins and then filling in details, in which the heads become the descents. The coins are a statement about the distribution, not a construction of the objects, and that is precisely what makes the real roots informative: they reveal an independence the combinatorics does not display.

When the coins can be seen #

For some statistics the coins are visible in the construction, and the comparison shows what the roots add.

The number of cycles of a permutation is counted by $x(x+1)(x+2)\cdots(x+n-1)$, the generating polynomial of the Stirling numbers of the first kind. Its roots are $0, -1, -2, \ldots$, so its coins have chances $1, \tfrac12, \tfrac13, \ldots, \tfrac1n$. And here the coins can be seen. Build a permutation by inserting the numbers $1, 2, \ldots, n$ one at a time, each either starting a new cycle or being placed after an existing entry in some cycle; the $k$-th number starts a new cycle with chance $1/k$, independently of what came before. The cycle count is the number of new cycles started, and the product formula is that construction written as a polynomial. The same polynomial comes out of the exponential formula, which builds a permutation as a set of labelled cycles and marks each cycle with the extra variable; there the product appears as the coefficient of $x^n/n!$ in $(1 - x)^{-y}$, and the coins are its factors.

The same coins give a familiar corollary: the number of cycles of a random permutation of $n$ is about $\log n$ on average, since $1 + \tfrac12 + \cdots + \tfrac1n$ grows like the logarithm. A random permutation of a thousand things has about seven and a half cycles, and one of them is usually very long — the cycles are as uneven as the question of who gets their own hat suggests, with a few large cycles and a scattering of small ones. For cycles, the polynomial was a product before anyone looked at its roots. For descents, the roots are the only evidence of the coins.

The bell curve follows #

A sum of many independent coins, none of them nearly certain, has a distribution close to normal. That is the central limit theorem, and in its simplest form it is the pile of balls under a board of pegs, where every coin is fair. Unequal coins are no obstacle so long as their variances keep adding up.

For descents the variances of the coins add up to $(n+1)/12$, which grows without bound, so the descent count is asymptotically normal. The figure shows the convergence at three sizes, and the largest gap between the cumulative distributions roughly halves each time $n$ doubles. This route to the central limit theorem through real roots is due to Lawrence Harper, who used it in 1967 for the Stirling numbers of the second kind — the number of blocks in a random set partition — where, as for descents, no coins are visible in the objects.

Harper’s method is worth stating as a method, because it applies far beyond descents. To show that a combinatorial statistic is asymptotically normal, show that its generating polynomial has only real roots, and check that the variance grows. The first step is often the hard one — it is a statement about a polynomial’s roots, not about the objects — but when it succeeds, independence has been proved without being exhibited.

Roots that are not real #

The inversion count is also a sum of independent pieces, and its polynomial is also a product. But the product is of a different kind, and its roots show the difference.

The factor $1 + q + \cdots + q^{k-1}$ vanishes at the $k$-th roots of unity other than one, so the inversion polynomial’s roots all lie on the unit circle, and almost none of them are real. Each factor is still a generating function of an independent piece — the number of earlier items a newly inserted item is placed before — but each piece is spread evenly over $0, 1, \ldots, k-1$ rather than being a coin. A uniform choice among $k$ values is not a sum of coins, and its polynomial has complex roots.

So both statistics are sums of independent parts and both are asymptotically normal, but they are different kinds of sum. The difference is invisible in the bell curves and visible in the roots, and it has consequences for the coefficients.

Inequalities that real roots force #

The coefficients of a polynomial with only real roots satisfy a family of inequalities found by Isaac Newton. If the polynomial is $\sum a_k x^k$ of degree $d$, then

$$a_k^2 \;\ge\; a_{k-1}\, a_{k+1} \left(1 + \frac1k\right)\left(1 + \frac1{d-k}\right)$$

for every $k$ strictly between $0$ and $d$. They are the same inequalities as between successive averages of the roots — the kind of fact about a polynomial its coefficients already know without its roots being found.

The descent row of ten keeps every one of Newton’s inequalities, as it must. The inversion row of six breaks every one, sitting at about $0.8$ to $0.87$ throughout. That is not a failure of smoothness: the inversion row is still log-concave in the plain sense, $a_k^2 \ge a_{k-1} a_{k+1}$, and it rises to a single peak and falls. What it lacks is the extra margin that real roots force.

This is the practical use of real-rootedness in combinatorics. Log-concavity and unimodality of a sequence are often conjectured and hard to prove directly, and a proof that the generating polynomial has only real roots gives both at once, with Newton’s stronger version for free. Many such proofs go through interlacing, as Frobenius’s did for descents. The link runs one way only. Real roots imply the inequalities, and the inversion row shows that a sequence can be log-concave, unimodal and asymptotically normal without them.

There is a second, older way to read a polynomial’s roots from its coefficients, and it points the same direction. Descartes’ rule of signs bounds the number of positive roots by the number of sign changes in the coefficients; for a counting polynomial, whose coefficients are all positive, it says there are no positive roots at all. Every real root of a counting polynomial is therefore negative, and the whole question of whether it is a sum of coins is whether its roots are real. Newton’s inequalities are the test that most often fails first, and a single failure — as with the inversions — is enough to rule the coins out.

What the computation cannot show #

The roots are found exactly in the sense that matters: the sign of the polynomial at each test point is computed in whole numbers, so every sign change is certain, and a count of sign changes equal to the degree proves that every root is real. The positions of the roots are then bisected to many digits, but they are approximations, and the coin chances derived from them carry that approximation. The match between coins and counts is therefore verified to nine decimal places, not proved exact by the figure; the exactness is the algebraic identity written above.

The checks are at $n = 10$ and $n = 20$ for the roots, and at $4$, $8$, $16$ for the bell curve. The theorems behind them — Frobenius’s real-rootedness, Harper’s method, Newton’s inequalities — cover every $n$, and the figures confirm them at the sizes drawn.

And the coins are not a construction. Nothing here produces a random permutation from nine coin tosses. Whether there is a natural one — some procedure building a permutation in which independent events with chances $1/(1 - r_i)$ produce exactly the descents — is not answered by the roots, and for descents none is known.

Still open: which polynomials in combinatorics have real roots #

Real-rootedness is known for many generating polynomials in combinatorics and conjectured for many more, and the conjectures have a way of lasting. Whether the polynomial counting forests or independent sets or matchings of a given size has only real roots depends on the family: for matchings it is a theorem of Heilmann and Lieb from 1972; for independent sets of a general graph it is false; for the coefficients of a graph’s chromatic polynomial, the weaker log-concavity conjecture of Read and Hoggar stood for forty years until June Huh proved it in 2012 by methods from algebraic geometry.

Behind the individual cases is a question with no general answer: when does a sequence defined by counting have a generating polynomial with only real roots? Interlacing, total positivity and the theory of stable polynomials each settle large families, and none settles the question in general. The descent polynomial is the model case, and its proof by interlacing is short; for most statistics nobody knows whether such a proof exists.

What the roots were counting #

A descent is a local event in a permutation, and the descents of a permutation are not independent of each other — two adjacent descents are less likely than two separated ones. Nothing suggests that their total is a sum of independent coins, and it is not in any constructive sense. But the distribution of that total is exactly the distribution of such a sum, and the only witness is the location of the roots of a polynomial.

That is the fourth thing a generating function can do, after counting, combining and tracking a statistic: its roots, if they are real, factor the statistic into independent coins. When they are not real, as for inversions, the factorisation — if there is one — is of another kind, and the coefficients carry the difference.