Hi everyone!
Today I want to write about the inversions in permutations. The blog is mostly inspired by the problem С from Day 3 of 2022 winter Petrozavodsk programming camp. I will also try to shed some light on the relation between inversions and $$$q$$$-analogs.
Key results
Let $$$F(x)=a_0+a_1x+a_2x^2+\dots$$$, then $$$F(e^x)$$$ is the exponential generating function of
In other words, it is a moment-generating function of the parameter by which $$$F(x)$$$ enumerates objects of class $$$F$$$.
Motivational example:
The generating function of permutations of size $$$n$$$, enumerated by the number of inversions is
The moment-generating function for the number of inversions in a permutation of size $$$n$$$ is
Model problem
Let $$$inv(p)$$$ be the number of inversions in permutation $$$p$$$. You're given $$$n$$$ and $$$k$$$, calculate
Direct solution
First thing one should notice to solve it is that
This is due to the fact that when you insert $$$(n+1)$$$ in the permutation $$$q$$$ of $$$n$$$, the number of inversions increases by $$$n-i$$$, where $$$i$$$ is the index of $$$(n+1)$$$ in the new permutation. Expanding this expression, we get
which rewrites in $$$d$$$-terms as
Let's denote the moment-generating function of $$$inv(q)$$$ over $$$S_n$$$ as
then the equation above rewrites as
with the base case $$$G_1(x) = 1$$$, where
So, the explicit expression for $$$G_n(x)$$$ is
This formula right away allows to calculate $$$d_n(k)$$$ for all $$$n \leq N$$$ and $$$k \leq K$$$ in $$$O(NK \log K)$$$.
$$$q$$$-analogs
General idea of $$$q$$$-analogs is to generalize some expression with the new parameter $$$q$$$ such that it is identical to the initial expression as $$$q \to 1$$$. One noteworthy example of $$$q$$$-analogs that you may be familiar with from competitive programming is the subset convolution:
We want to multiply polynomials in $$$R[x_1, \dots, x_n] / \langle x_1^2, \dots, x_n^2\rangle$$$. As this is non-trivial, we instead multiply them in
or
With $$$q \to 1$$$ we may see that the first ring gives the $$$q$$$-analog of xor-convolution (Walsh-Hadamard transform), while the second expression is the $$$q$$$-analog of or-convolution (Möbius transform). And $$$q \to 0$$$ gives us the subset convolution in both cases.
$$$q$$$-factorials
$$$q$$$-analog of a positive integer number $$$n$$$ is typically defined as
From this expression, we may derive the so-called $$$q$$$-factorial:
This expression should already be familiar to us, as with $$$q \to e^x$$$ it is the moment-generating function for the number of inversions. On the other hand, with $$$q \to 1$$$ this expression is simply equal to $$$n!$$$, thus it's natural to assume that $$$[n]_q!$$$ enumerates permutations in some way.
Consider the generating function for the permutations of length $$$n$$$ enumerated by the number of inversions:
It means that $$$[n]_q!$$$ in fact, enumerates permutations of $$$S_n$$$ grouped by the number of inversions. In other words,
Moment-generating function
Let $$$F(x)=a_0 + a_1 x + a_2 x^2 + \dots$$$ be the ordinary generating function for the sequence $$$a_0, a_1, \dots$$$, then
In other words, $$$F(e^x)$$$ is the EGF for
which is the $$$i$$$-th moment of the number by which $$$F(x)$$$ enumerates objects of class $$$F$$$. For $$$F_n(x)$$$, all permutations $$$p \in S_n$$$ are enumerated by $$$inv(p)$$$, thus $$$G_n(x)=F_n(e^x)$$$ is the moment-generating function for the number of inversions of $$$p \in S_n$$$.
$$$q$$$-Pochhammer symbol
$$$q$$$-Pochhammer symbol is defined as
as (almost) the $$$q$$$-analog of the regular Pochhammer symbol
With $$$q$$$-Pochhammer symbol, expressions for $$$F_n(x)$$$ and $$$G_n(x)$$$ can be simplified to
and
Sorry, I can't provide any explanation on why it's useful, but it looks pretty.
Bonus:
Assume that you need to calculate the expected value of $$$inv(p)^k$$$ over $$$|p|=n$$$ with a relatively small $$$k$$$ and a large $$$n$$$. Then you can do it in $$$O(k^2 \log k)$$$ pre-processing and $$$O(k)$$$ for every $$$n$$$ with a fixed $$$k$$$. Deriving specific solution is left to the curious reader as an exercise.
Questions to the audience:
- Can anyone get rid of this nasty $$$\log k$$$? Or do the pre-processing without FFT?
- Is there a meaningful expression for OGF or EGF of $$$d_n(k)$$$ where powers of $$$x$$$ traverse through $$$n$$$ rather than $$$k$$$?