Matpic
mathematics, in pictures
Series

Generating functions — the series

4 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

All series