The coefficient that is a polynomial

A polynomial that counts hangs one number on each power of $x$: how many objects of that size there are. The number is the answer to the question, and it is also everything the construction is allowed to remember.

That is a severe restriction and it is easy to miss, because the question usually asked is how many. There are twenty-four permutations of four things. It is a true and complete answer to one question and it is silent about every other question anybody might ask of those twenty-four objects — whether most of them are nearly sorted, how many transpositions the typical one needs, whether the worst is far from the average. Adding one variable makes all of those available without giving up the count.

What the second variable records #

Pick a statistic: a whole number attached to each object. For a permutation, take its number of inversions — the pairs of positions holding values in the wrong order, which is $0$ for the identity and $\binom{n}{2}$ for the full reversal. Now build a series in two variables,

$$F(x, q) = \sum_{\text{objects}} x^{\,\text{size}}\, q^{\,\text{statistic}},$$

so that the coefficient of $x^n$ is no longer a number but a polynomial in $q$, one term for each value the statistic takes.

The hero figure is that polynomial written out as a row of coefficients, at the first five sizes. At $n = 4$ the row reads $1, 3, 5, 6, 5, 3, 1$: one permutation of four with no inversion, three with exactly one, and so on up to one with all six. It adds to twenty-four.

The addition is the whole reason this costs nothing. Setting $q = 1$ replaces every $q^k$ by $1$, which adds the row, which gives back the one-variable coefficient. So the two-variable series contains the one-variable one as a special case and the count is never at risk. Everything the rest of this essay reads off the rows is extra information sitting in a place the earlier construction left empty.

The rows have names #

The row at $n = 4$ is not an arbitrary list. It is the coefficient list of

$$[4]_q! = (1)(1+q)(1+q+q^2)(1+q+q^2+q^3),$$

and the general statement is that the inversion-counting polynomial for $S_n$ is the product $\prod_{j=1}^{n}(1 + q + \cdots + q^{j-1})$ — the q-factorial. Setting $q = 1$ turns each factor $1+q+\cdots+q^{j-1}$ into $j$ and the product into $n!$, which is the check above and also a proof that the row adds correctly.

The factorisation comes from building a permutation one entry at a time. Inserting the largest value into a permutation of the rest can be done in $j$ places when there are $j$ positions available, and inserting it $i$ places from the right creates exactly $i$ new inversions and disturbs none of the old ones. So each insertion contributes an independent factor $1 + q + \cdots + q^{j-1}$, and the product is the series.

That argument is worth pausing on because it is the kind this bookkeeping makes routine. The claim — the inversion statistic factorises over the insertions — is a statement that one choice does not interfere with another, and the whole of the algebra is the observation that independent choices multiply. It is the same sentence the ordinary product rests on with a statistic carried along.

The mean is a derivative #

Write $P_n(q)$ for the row at size $n$. Then $P_n(1)$ is the count, and

$$P_n'(1) = \sum_k k\, a_k$$

is the total of the statistic over all the objects, because differentiating $q^k$ gives $kq^{k-1}$ and setting $q=1$ leaves $k$. So the mean of the statistic is $P_n'(1)/P_n(1)$ — two evaluations of one polynomial, and no averaging.

For inversions the answer is $n(n-1)/4$ and the derivation is one line from the factorisation. Each factor $1+q+\cdots+q^{j-1}$ contributes, by the product rule, its own mean $\frac{0+1+\cdots+(j-1)}{j} = \frac{j-1}{2}$; summing over $j$ from $1$ to $n$ gives $\frac{1}{2}\binom{n}{2}\cdot\frac{2}{1}$, which is $n(n-1)/4$. Independence again, and this time it is doing something the count could not do: the mean of a sum of independent contributions is the sum of their means, and the factorisation is what makes the contributions independent.

Half the maximum, which is $\binom{n}{2}$, is the same number — so the average permutation has half the inversions the reversal does, which is the answer symmetry would have guessed. Symmetry does guess it correctly here, because reversing a permutation swaps $k$ with $\binom{n}{2}-k$ and so the row is palindromic; the row at $n=4$, $1,3,5,6,5,3,1$, is. What symmetry cannot give is the variance, and the second derivative does: $\mathrm{Var} = n(n-1)(2n+5)/72$, from summing the variances $\frac{j^2-1}{12}$ of the individual factors.

A statistic whose distribution is not symmetric #

The device is not about permutations. Track the number of parts in a partition and the two-variable series is Euler’s product with a $q$ inserted,

$$\prod_{j\ge1}\frac{1}{1 - q x^j},$$

where the $q$ counts one for each part used. Setting $q = 1$ gives the product the counting polynomial ends on, so again nothing is lost.

The rows here are not palindromic and there is no reason they should be. A partition of six can have between one and six parts, and the counts $1, 3, 3, 2, 1, 1$ are lopsided — most partitions of six use two or three parts, and exactly one uses six. The distribution’s asymmetry is a fact about partitions and the one-variable count cannot express it, since eleven is eleven.

That asymmetry is what makes the mean worth computing rather than guessing. Averaging the number of parts over the partitions of six gives $\frac{1\cdot1+2\cdot3+3\cdot3+4\cdot2+5\cdot1+6\cdot1}{11} = \frac{35}{11}$, which is about $3.18$ — not the midpoint of one and six, and not deducible from any symmetry. The derivative computes the same thirty-five without listing anything, which is the point of having it: differentiating Euler’s product with the $q$ in it and setting $q=1$ gives the total number of parts over all partitions of $n$, and that total is a quantity with a life of its own — it equals the sum over $j$ of the number of partitions of $n$ containing at least one part $j$, which is a second reading of the same number and a small instance of counting one collection two ways.

The shape is the thing the count hid #

A row of a two-variable table is a distribution, and looking at one is the quickest way to see what the second variable has bought. The inversion rows pile up in the middle and thin out at both ends. As $n$ grows they get relatively narrower — the standard deviation grows like $n^{3/2}$ while the range grows like $n^2$ — and the shape approaches a bell, for the reason a sum of many independent things does: the inversion count is such a sum, one summand per insertion, and the factorisation above is the statement that the summands are independent.

Putting the two pictures side by side is the argument for drawing either. The two statistics come out of the same machine, are read off the same kind of table, and behave completely differently — one converging to a bell and one not — so the shape is a property of the objects and the statistic rather than of the method. A reader who has only seen the inversion table is liable to expect a bell; the partition table is the cheapest available correction.

Why the permutation rows read the same backwards #

The inversion row at $n=4$ is $1,3,5,6,5,3,1$, and the palindrome is not an accident of a small case. Reversing a permutation — writing its entries in the opposite order — turns a pair that was in the right order into one in the wrong order and the other way about, so it sends a permutation with $k$ inversions to one with $\binom{n}{2}-k$. That is a bijection from the objects with $k$ to the objects with $\binom{n}{2}-k$, so the two counts are equal, and the row reverses to itself.

The argument is worth having in full because it is short and because it is the kind that a table cannot supply. A reader who checks the row at $n=4$ has verified one instance; the reversal is what covers every $n$, and it is an involution — applying it twice gives back the permutation started with — which is why the pairing is between the two ends rather than a shuffle within the row.

It also gives the mean without a derivative. A palindromic distribution is symmetric about the middle of its range, so its mean is $\frac{1}{2}\binom{n}{2} = n(n-1)/4$, agreeing with the calculation above. Two routes to one number, one from a factorisation and one from a symmetry, and the agreement is the check the figure’s third column reports. The variance is where the two routes part: symmetry says nothing about it, and the factorisation gives it in a line, which is the honest reason to prefer the factorisation as the primary tool.

The sign of a permutation is the parity of its inversion count, so the row also answers a question about the symbol that is the sign of a shuffle: adding the even-indexed entries of the row gives the number of even permutations. At $n = 4$ that is $1+5+5+1 = 12$, which is half of twenty-four, and the palindrome is what makes it exactly half whenever $\binom{n}{2}$ is odd or the row has a matching middle.

The same row from a definition with nothing in common #

Define a second statistic: for each position where a permutation steps down — where the entry after is smaller than the entry before — add up the position numbers. That is the major index, it has nothing visibly to do with counting pairs out of order, and its distribution is identical to the inversion distribution at every size.

That is MacMahon’s theorem, and the figure is the check rather than the proof. The two definitions look at different things: inversions consider every pair of positions, the major index only the adjacent descents, and a single permutation usually gets two different numbers from them. At $n=5$, ninety-two of the hundred and twenty do.

An equidistribution is a much stronger statement than an equality of totals and a much weaker one than a bijection. Both statistics have $n!$ objects underneath them, so their rows adding to the same number is worth nothing; what is being claimed is that they agree column by column. And the claim is about counts rather than about objects, so it leaves open the question of which permutation with major index three corresponds to which permutation with three inversions. Foata gave a bijection in 1968 that answers it — a construction on the permutation that changes the major index into the inversion count — and finding it took sixty years after MacMahon had the identity.

A statistic distributed like the inversion count is now called Mahonian, and several are known. That a name was needed is the tell that the phenomenon is common rather than isolated, and the explanation in every case is a bijection rather than an algebraic manipulation: the polynomial is the same polynomial, so no amount of rearranging one definition turns it into the other.

Two variables, and where the second one came from #

The construction has a name in the literature and the name is worth knowing, because it is where the rest of the subject is filed. A polynomial in $q$ that becomes a familiar count at $q = 1$ is a q-analogue of that count, and the standard ones are exactly the ones above: $[n]_q!$ for $n!$, and the Gaussian binomial

$$\binom{n}{k}_q = \frac{[n]_q!}{[k]_q!\,[n-k]_q!},$$

which is a polynomial in $q$ — not obviously, since it is written as a quotient — whose value at $q=1$ is $\binom{n}{k}$ and whose coefficients count the partitions fitting inside a $k \times (n-k)$ box. $\binom{4}{2}_q = 1 + q + 2q^2 + q^3 + q^4$, which adds to six.

The figure is worth reading for what it does not show. A quotient of polynomials is a polynomial only if the division comes out, and the definition gives no reason it should — the numerator has degree $\binom{n}{2}$ and the denominators between them have the same degree, so the leading terms cancel and everything after that has to be checked. What the figure computes instead is the partition count, which is a whole number by construction, and the agreement of that count with the quotient is the theorem.

The rows are palindromic for the same kind of reason the inversion rows were: complementing a partition inside its box — taking the cells the partition does not occupy, rotated — pairs the partitions of area $a$ with those of area $k(n-k)-a$. So the degree of the polynomial is $k(n-k)$, which the figure checks, and the largest coefficient sits in the middle. The coefficients being unimodal is a genuinely hard theorem, proved first by Sylvester in 1878 by an argument nobody found easy, and it is invisible in the definition.

Both of those are visible in the tables above: the $q$-factorial is the last row of the hero figure, and the Gaussian binomials are what the second table lists. The pleasant thing about the pair is that the second is built from the first, exactly as the ordinary binomial coefficient is built from the ordinary factorial, so the whole of elementary counting has a $q$-shadow with the same shape and one extra variable. Pascal’s triangle has one too: $\binom{n}{k}_q = \binom{n-1}{k-1}_q + q^{k}\binom{n-1}{k}_q$, which is the ordinary recursion with a power of $q$ marking which of the two ways the new element was treated.

The Catalan case is where the pattern stops being tidy. Tracking the area under a balanced path gives a polynomial that adds to the Catalan number, and it satisfies a recurrence in two variables; what it does not have is a factorisation into short factors of the kind the $q$-factorial has. So the same construction produces a rigid formula in one case and an awkward recurrence in another, and which happens is not predictable from the definition.

What the extra variable costs #

Nothing is lost and the expressions get longer. Every closed form in the one-variable theory has to be re-derived, and some do not survive. $1/(1-x-x^2)$ is a rational function; its $q$-analogue tracking some statistic on the tilings need not be rational in $x$ at all, and the poles the earlier essay reads growth rates off may simply not be there.

The coefficients are polynomials and the extraction is harder. Asking for the number of permutations of ten things with exactly twenty inversions is asking for one coefficient of a polynomial of degree forty-five, and there is no closed form for it — there is a generating function, which is the point, and reading a single coefficient out of it is a computation.

The statistic has to be chosen and nothing suggests which. Inversions and the major index are two of a dozen statistics on permutations that somebody found worth naming, and there is no procedure that produces them — the device takes a statistic and reports its distribution, and choosing one that has a product formula or an equidistribution partner is the part that needs a person. That is the same complaint the ordinary dictionary invites about decompositions, one level up.

And two variables is where the cases multiply. A statistic may or may not factorise, may or may not be symmetric, may or may not concentrate; the machine accepts all of them equally and gives no indication which has happened. Every claim in this essay about a shape was read off an enumeration rather than deduced, which is a confession about the method as much as about the figures.

What the pictures cannot show #

The tables stop at five or six. The inversion table at $n = 10$ has forty-six columns and $3{,}628{,}800$ objects behind it, and neither the row nor the enumeration that checks it would fit or finish. Everything drawn here is small enough to be verified by listing, which is what makes the figures evidence about the objects and not about the algebra — and it is also what makes them silent about the limit the bar charts are heading towards.

The bars are drawn at three sizes and the claim about the bell shape is asymptotic. Three panels cannot distinguish a distribution converging to a bell from one converging to something slightly different, and the figures do not try: what they check is that each row rises to a peak and falls, which is a claim a drawn row can fail.

And the palindromic rows are drawn as numbers, so the symmetry has to be read rather than seen. A reader checking that $1,3,5,6,5,3,1$ reverses to itself is doing arithmetic; the corresponding reason — that reversing a permutation complements its inversion count — is a sentence about the objects that no table contains.

Still open: which statistics have product formulas #

Two of the statistics here factorise and one does not, and the general question of which do is open in the form anybody would want it. What is known is a sufficient condition: a statistic that can be written as a sum of contributions from independent choices in some construction of the objects will factorise over those choices, which is what inversions do over insertions and what the number of parts does over Euler’s factors.

What is not known is a characterisation. There are statistics with unexpected product formulas — the major index on permutations has the same distribution as inversions, a theorem of MacMahon’s that is not obvious from either definition — and statistics with no formula at all, of which the Catalan area is the standing example. Explaining a coincidence of distributions between two statistics defined in unrelated ways is a live subject, and the usual form of an explanation is a bijection that carries one statistic to the other, which is the same kind of object as the one that matches two collections and is usually much harder to find than the identity it proves.

What the variable was tracking #

The count is one number and the objects are many. Squeezing many objects into one number throws information away, and the interesting observation is that it is possible to throw away less without paying for it: the two-variable series contains the one-variable one exactly, at $q = 1$, and everything else it holds is free.

That is the general shape and it is not confined to generating functions. A statistic on a family of objects is a refinement of the count, and a refinement is safe as long as there is an operation that collapses it back — here, adding a row. What makes the refinement worth having is that the collapsed version cannot answer questions the refined one can: a mean, a variance, a shape, or the fact that two statistics defined differently are distributed identically.

The cost is that the questions get harder, and the discipline is the one the counting polynomial already stated. Every row in every table here was checked against a list of the objects, because a bookkeeping device that tracks two things can be internally consistent and describe nothing — and adding a variable doubles the number of places a decomposition can quietly go wrong.