Moment-generating function for the number of inversions

Правка en1, от adamant, 2022-02-04 02:58:55

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

$$$d_n(k) = \sum\limits_{p \in S_n} inv(p)^k.$$$

First thing one should notice to solve it is

$$$\sum\limits_{p \in S_{n+1}} inv(p)^k = \sum\limits_{i=0}^n \sum\limits_{q \in S_n} (inv(q)+i)^k.$$$

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

$$$ \sum\limits_{p \in S_{n+1}} inv(p)^k = \sum\limits_{i=0}^n \sum\limits_{j=0}^k \binom{k}{j} i^{k-j{}} \sum\limits_{q \in S_n} inv(q)^j, $$$

which rewrites in $$$d$$$-terms as

$$$ \frac{d_{n+1}(k)}{k!}=\sum\limits_{j=0}^k \left(\frac{d_n(j)}{j!} \right) \left(\sum\limits_{i=0}^n \frac{i^{k-j{}}}{(k-j)!}\right). $$$

Let's denote the moment-generating function of $$$inv(q)$$$ over $$$S_n$$$ as

$$$G_n(x) = \sum\limits_{t=0}^\infty x^t\sum\limits_{q \in S_n} \frac{inv(q)^t}{t!} = \sum\limits_{t=0}^\infty \frac{x^t d_n(t)}{t!},$$$

then the equation above is rewritten as

$$$G_{n+1}(x) = G_n(x) A_n(x),$$$

with the base case $$$G_1(x) = 1$$$, where

$$$A_n(x) = \sum\limits_{t=0}^\infty x^t\sum\limits_{i=0}^n \frac{i^t}{t!} = \sum\limits_{i=0}^n e^{ix} = \frac{1-e^{(n+1)x}}{1-e^x}.$$$

So, the explicit expression for $$$G_n(x)$$$ is

$$$G_n(x) = \prod\limits_{t=1}^{n} \frac{1-e^{tx}}{1-e^x}.$$$

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:

  1. Can anyone get rid of this nasty $$$\log k$$$? Or do the pre-processing without FFT?
  2. 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

$$$G(x, y) = \sum\limits_{n=0}^\infty \prod\limits_{t=1}^n y\frac{1-e^{tx}}{1-e^x}$$$
Теги generating function, inversions, q-analog, polynomials, tutorial, power series

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский adamant 2022-02-05 14:19:20 117 link
en7 Английский adamant 2022-02-04 21:29:35 1 Tiny change: '= [n+1]_x!.$$\n\nIt m' -> '= [n+1]_x!$$\n\nIt m'
en6 Английский adamant 2022-02-04 21:27:37 6 Tiny change: 'increases with $n-i$, wh' -> 'increases by $n-i$, wh'
en5 Английский adamant 2022-02-04 21:18:01 2 Tiny change: '\n\n[cut]<hr>\n\n####' -> '\n\n[cut]<br>\n\n####'
en4 Английский adamant 2022-02-04 21:17:40 13 Tiny change: 'x}.$$ \n\n#### M' -> 'x}.$$ \n\n[cut]\n\n#### M'
en3 Английский adamant 2022-02-04 21:16:58 2 typo
en2 Английский adamant 2022-02-04 21:09:02 4321 Tiny change: 'sions and q-analogs.' -> 'sions and $q-analogs.' (published)
en1 Английский adamant 2022-02-04 02:58:55 2502 Initial revision (saved to drafts)