Series

Generating functions — the series

7 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. A product of 3 polynomials, and what its coefficients count. The coefficients of a product of small polynomials, with the combinations of choices that reach one marked total written out beneath it.

    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.

    part 1 · discrete
  2. The 6 ways to deal 4 labels between pieces of size 2 and 2. Every way of splitting 4 labels between a piece of size 2 and a piece of size 2, listed as two rows of boxes each. The count is the binomial coefficient that distinguishes a labelled product from an ordinary one.

    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.

    part 2 · discrete
  3. Permutations of n things, by how many pairs they put in the wrong order. A table whose row n and column k hold the number of permutations of size n whose inversions is k, with each row's total beside it — the plain count the one-variable series gives.

    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.

    part 3 · discrete
  4. Descents of 10 as a sum of 9 hidden coins. Bars of 9 coin probabilities beside a bar chart of the descents distribution for n = 10, with dots giving the coin-sum distribution landing on every bar.

    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.

    part 4 · discrete
  5. A spider's matchings have real roots and its independent sets do not. Spider with legs 3, 3, 3: matching polynomial 1, 9, 27, 32, 12, roots -0.5000, -0.2324, -0.5000, -1.4343; independence polynomial 1, 10, 36, 57, 38, 9, 1, 4 non-real roots.

    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.

    part 5 · discrete
  6. A chromatic polynomial with complex roots and log-concave coefficients. Wheel W5: P(x) = x⁶ − 10x⁵ + 40x⁴ − 80x³ + 79x² − 30x; |coefficients| 30, 79, 80, 40, 10, 1; min ratio 2.0000; roots 3.000, 0.000, 2.000−1.000i, 2.000, 1.000, 2.000+1.000i.

    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.

    part 6 · discrete
  7. The forests of a complete graph on four points. K4 forests by size: 1, 6, 15, 16; ratios 2.4000, 2.3438.

    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.

    part 7 · discrete

All series