A product of 3 polynomials, and what its coefficients count
genfun is one function. Everything below came out of it during this
build, at parameters taken from the essays rather than invented for this page — so a figure
here is the same figure a reader meets in an essay, and if the generator changes, this page
changes with it.
With nothing chosen
Multiplying two series is summing a diagonal
1 / (1 − x − x²), and the objects its coefficients count
Where the descent polynomial of 10 vanishes
Descents of 10 as a sum of 9 hidden coins
Descents settle onto the bell curve
What it checks while it draws
Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.
- at size 1 the two statistics give the same count at value 0 ×25
- the coefficient of x^0 is the number of combinations totalling 0 ×10
- the coefficient of x^0 is the number of objects of size 0 ×9
- the coefficient of xᵐ/m! at m = 0 is the number of objects on 0 labels ×8
- claw-free graphs on 3 vertices with a non-real independence root ×7
- graphs on 3 vertices whose matching polynomial has a non-real root ×7
- the coefficient of x^0 is the sum along its diagonal ×7
- row 1 adds to the plain count at that size ×6
- the row for k = 0 adds to the ordinary binomial coefficient ×6
- the row for k = 0 has degree k(n − k) ×6
- at size 1 the derivative at q = 1 is the total of the statistic over the objects ×5
- the mean number of inversions at n = 1 is n(n − 1)/4 ×5
- the bars at size 3 add to the plain count ×4
- the series is drawn to between 5 and 10 terms ×2
- a chromatic coefficient sequence rises to one peak and falls (Read's unimodality) ×1
- a sequence of singletons on n labels is a permutation of them ×1
- an ordered pair on n labels is a two-way split of them ×1
- and the exact sign search does not find them all on the negative axis ×1
- and the marked coefficient counts the combinations written out beside it ×1
- as many sign changes on the negative axis as the degree: every root is real and negative ×1
- at k = 1 the counts are 1, m and C(m, 2), exactly binomial ×1
- at least one coefficient exceeds one, so the polynomial is not merely a string of ones ×1
- at some coefficient the ratio falls below what real roots would require ×1
- between two and four boxes, each offering between two and five whole-number values ×1
- between two and four sizes, each one this statistic is enumerated at ×1
- both label-counts are short lists of small whole numbers ×1
- both series are short lists of small whole numbers ×1
- each root of unity is a root of the inversion polynomial ×1
- each root's reciprocal is a root ×1
- equality holds only where every set of k − 1, k and k + 1 edges is a forest ×1
- every combination of choices is listed ×1
- every root lies within 2√(Δ − 1) = 2√2 for a graph of largest degree three ×1
- every sampled graph's edge count lies on the drawn axis ×1
- every small graph satisfies all three of Mason's inequalities ×1
- its coefficients are nevertheless log-concave ×1
- no real chromatic root is negative, between 0 and 1, or between 1 and 32/27 ×1
- on six points some forest polynomials have roots off the real line ×1
- one root for each unit of degree ×1
- random graphs on nine points satisfy the strongest inequality ×1
- so the chromatic roots of this graph are not all real ×1
- some graph with a claw has an independence polynomial with non-real roots ×1
- the bound is exact at k = 2 exactly when the graph has no triangle ×1
- the checked size is between 3 and 6 ×1
- the chromatic coefficients are log-concave on every graph ×1
- the coefficient at size 4 counts a deal of the labels together with a structure on each side ×1
- the coefficients are log-concave ×1
- the coins give mean (n − 1)/2 and variance (n + 1)/12 ×1
- the complete graph on four points has 1, 6, 15 and 16 forests with 0 to 3 edges ×1
- the counts rise to one peak and fall away from it ×1
- the deal is a choice rather than a formality — the ordinary product would count one ×1
- the descent row satisfies every one of Newton's inequalities ×1
- the distance to the bell falls as n grows ×1
- the drawn graph's matching polynomial is real-rooted ×1
- the drawn matching roots are real and negative ×1
- the first piece takes between 1 and n − 1 of them ×1
- the four rows give four different counts, so the table is separating the constructions ×1
- the inversion row fails every one ×1
- the labelled count exceeds the unlabelled one, which is what the binomial buys ×1
- the labelled family is one this family knows ×1
- the labelled object has between 3 and 6 labels ×1
- the largest matching root is at most 2√(d − 1) ×1
- the last row is spread over more than one value, so the statistic is doing something ×1
- the marked coefficient is a small whole power ×1
- the marked coefficient is inside the product ×1
- the marked size is inside both series ×1
- the marked total is one the boxes can reach ×1
- the matching sizes are exactly a sum of independent coins ×1
- the mean grows with the size, so the reading is not a constant ×1
- the Petersen graph has claws and a real-rooted independence polynomial all the same ×1
- the recurrence agrees with counting descents directly ×1
- the roots of the graph with a vertex removed interlace the graph's roots ×1
- the sequence is growing, so the check has content ×1
- the sequence is one the family knows ×1
- the series inverted has a non-zero constant term ×1
- the series is drawn to between 3 and 10 terms (20 for the root views) ×1
- the six-vertex wheel has non-real chromatic roots ×1
- the sizes drawn are between 3 and 5 ×1
- the sizes drawn are ones this statistic is enumerated at ×1
- the spider's matching polynomial is real-rooted and its independence polynomial is not ×1
- the statistic is descents or cycles ×1
- the statistic is one this family tracks ×1
- the sum of independent coins has exactly the counted distribution ×1
- the table is drawn to a size this statistic is enumerated at ×1
- the top of the coefficient is between 3 and 6 ×1
- the two statistics disagree on individual objects, so the agreement is of distributions ×1
- the value at q = 1 is the plain count ×1
- the view is one the family draws ×1
- there are 155 graphs with at least one edge on six points and 33 on five, up to isomorphism ×1
- there are C(4, 2) ways to deal the labels between the two pieces ×1
- though it is still log-concave in the plain sense ×1
- two different statistics this family tracks ×1
Where it is called
Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.
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.
DiscreteCoins 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.
NumberEvery partition, hidden in a product
Multiply out one factor for each part size and the coefficient of q to the n is the number of partitions of n. Nothing is being approximated: the product is a bookkeeping device that does the counting by multiplying.
DiscreteLog-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.
DiscreteThe 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.
DiscreteThe 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.
DiscreteThe 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.
DiscreteThe 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.