Generating functions — the series
-
A polynomial that counts
Hang a counting sequence on the powers of a variable and the two ways of combining choices — this and that, this or that — become multiplication and addition, so a recursion turns into an equation and the equation can be solved.
-
The product that deals the labels
Multiplying two counting series pairs one choice with another. When the things being counted carry labels, the labels have to be dealt out as well, and the only series that survive the extra bookkeeping are the ones divided by n factorial.
-
The coefficient that is a polynomial
Add a second variable to track a statistic and each coefficient stops being a number. Set the new variable to one and the old count comes back untouched; leave it in and the mean of the statistic is a derivative rather than an average.
-
Coins hidden in the roots
The polynomial that counts permutations by their descents has no product formula, and nothing in the definition of a descent is a coin toss. But every root of the polynomial is real and negative, and a polynomial like that is a product of coins in disguise: each root r is a coin landing heads with chance 1/(1 − r). The descent count of a random permutation is exactly a sum of independent coins nobody can point to — which is why it is bell-shaped, and why its coefficients obey inequalities the inversion count breaks.
-
The roots every matching polynomial keeps real
Count a graph's matchings by size and make the counts the coefficients of a polynomial. On every one of 35,664 graphs tested, that polynomial has only real roots — a theorem of Heilmann and Lieb from 1972. Count independent sets instead and the roots wander off the axis on a growing share of graphs, but never on a graph without a claw, and matchings are the independent sets of a graph that never has one.
-
Log-concave with nothing to make it so
The chromatic polynomial of a graph counts its colourings, and its coefficients rise to one peak and fall, each squared at least the product of its neighbours. For a real-rooted polynomial that would be automatic. But by nine vertices fewer than one graph in twenty has only real chromatic roots, and the coefficients stay log-concave anyway — on every graph tested, and, by June Huh's theorem of 2012, on every graph there is.
-
The forests a graph can hold
Count the sets of edges in a graph that contain no cycle, sorted by size, and the counts rise and fall in a single peak — more sharply peaked, John Mason conjectured in 1972, than the binomial coefficients with the same number of edges. On every graph with up to six points the strongest of his three inequalities holds, with equality exactly where cycles are too long to matter; on random graphs with nine points it holds with a margin of about one per cent. It was proved for every graph, and every matroid, in 2018.