Track inversions with a generating polynomial

Try

In the permutation 3, 1, 2, the label three appears before both smaller labels, creating two inversions. An inversion is a pair of positions i< j whose values satisfy π_i>π_j. Counting inversions measures disagreement with increasing order, but different permutations can have the same count. We will retain the entire distribution in a polynomial rather than summarize it by a single average.

Predict

Predict what happens when the largest label is inserted into a shorter permutation. It creates one inversion with every entry after it and none with entries before it. Its possible contribution is therefore any integer from zero through n−1, exactly once for each insertion position. The old inversions remain unchanged because the relative order of all old labels is preserved.

Experiment

List all permutations of three labels and group them by inversion count.

Count	Permutations	Coefficient
0	123	1
1	132, 213	2
2	231, 312	2
3	321	1

Thus the polynomial is 1+2q+2q²+q³=(1+q)(1+q+q²). Check the total at q=1 and the signed difference at q=−1. These evaluations answer different questions about the same coefficient distribution.

Understand

Define I_n(q)=Σ over permutations π of q^(inv (π)), with I_0(q)=1 for the empty permutation. The insertion bijection proves I_n(q)=(1+q+…+q^(n−1))I_(n−1)(q). Iteration gives the q-factorial product. Its degree is N=C(n, 2), the inversion count of the reverse permutation. Reversing the positions of any permutation changes every inverted pair into a noninverted pair and conversely, proving q^N I_n(1/q)=I_n(q) as a polynomial identity after clearing negative powers. This symmetry is a combinatorial involution, not an accidental numerical pattern in the first few rows.

Apply

A related q-enumeration counts binary words with r ones and s zeros, weighting a word by its number of one-before-zero pairs. Let F(r, s) be the polynomial. Splitting by the final letter gives F(r, s)=F(r−1, s)+q^r F(r, s−1), with F(0, s)=F(r, 0)=1. At q=1 this becomes the binomial recurrence and counts C(r+s, r) words. These are Gaussian binomial polynomials, a refinement of binomial coefficients. The recurrence proves that their coefficients are nonnegative integers even if a later quotient-of-products expression obscures that fact.

The Gaussian binomial also has the product expression F(r, s)=product from i=1 to r of (1−q^(s+i))/(1−q^i). To verify it without assuming polynomial division works, treat the expression as a rational function and check the boundary values and the proved recurrence. Dividing the two recurrence terms by the proposed product gives respectively (1−q^r)/(1−q^(r+s)) and q^r(1−q^s)/(1−q^(r+s)); their sum is one. Induction identifies the rational expression with the counting polynomial, proving its apparent denominators cancel.

Continue

Use insertion to construct a permutation with a specified inversion count: choose the number created at each stage, respecting its range. Explain why arbitrary independent counts outside those bounds do not decode. For a uniform random permutation, indicator variables give expected inversions N/2 because each label pair has either order with equal probability; pairwise independence is unnecessary. This lesson concerns a formal counting variable q, not a probability or a field size unless another interpretation is explicitly introduced.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with count unlabeled blocks of labeled objects.