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. The problem goes as follows:
Let $$$inv(p)$$$ be the number of inversions in permutation $$$p$$$. You're given $$$n$$$ and $$$k$$$, calculate
First thing one should notice to solve it is
This is due to the fact that when you insert $$$(n+1)$$$ in the permutation $$$q$$$ of $$$n$$$, the number of inversions increases with $$$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 is rewritten 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)$$$.
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$$$?
Let $$$G(x, y) = \sum\limits_{n=1}^\infty y^n G_n(x)$$$, then