Moment-generating functions, inversions and q-analogs

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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

$$$b_i = \sum\limits_{k=0}^\infty a_k k^i.$$$

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

$$$F_n(x) = \prod\limits_{k=1}^n \frac{1-x^k}{1-x}.$$$

The moment-generating function for the number of inversions in a permutation of size $$$n$$$ is

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

Model problem

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.$$$

Direct solution

First thing one should notice to solve it is that

$$$\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 by $$$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 rewrites 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)$$$.

$$$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

$$$R[q][x_1, \dots, x_n] / \langle x_1^2 - q^2, \dots, x_n^2 - q^2 \rangle$$$

$$$R[q][x_1, \dots, x_n] / \langle x_1^2 - x_1 q, \dots, x_n^2 - x_n q \rangle.$$$

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

$$$[n]_q = 1+q+\dots+q^{n-1} = \frac{1-q^{n}}{1-q}.$$$

From this expression, we may derive the so-called $$$q$$$-factorial:

$$$[n]_q! = [1]_q [2]_q \dots [n]_q = \prod\limits_{k=1}^n \frac{1-q^k}{1-q}.$$$

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:

$$$F_{n+1}(x) = \sum\limits_{p \in S_{n+1}} x^{inv(p)} = \sum\limits_{i=0}^n \sum\limits_{p \in S_n} x^{inv(p)+i} = \sum\limits_{i=0}^n x^i F_n(x) = \frac{1-x^{n+1}}{1-x} F_n(x) = [n+1]_x!$$$

It means that $$$[n]_q!$$$ in fact, enumerates permutations of $$$S_n$$$ grouped by the number of inversions. In other words,

$$$F_n(q) = \prod\limits_{k=1}^n \frac{1-q^k}{1-q} = [n]_q!$$$

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

$$$F(e^x) = \sum\limits_{k=0}^\infty a_k e^{kx} = \sum\limits_{k=0}^\infty a_k \sum\limits_{i=0}^\infty \frac{k^i x^i}{i!} = \sum\limits_{i=0}^\infty \frac{x^i}{i!} \sum\limits_{k=0}^\infty a_k k^i.$$$

In other words, $$$F(e^x)$$$ is the EGF for

$$$b_i = \sum\limits_{k=0}^\infty a_k k^i,$$$

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

$$$(a;q)_n = (1-a)(1-aq)(1-aq^2) \dots (1-aq^{n-1}),$$$

as (almost) the $$$q$$$-analog of the regular Pochhammer symbol

$$$(a)_n = a(a-1)\dots(a-(n-1)).$$$

With $$$q$$$-Pochhammer symbol, expressions for $$$F_n(x)$$$ and $$$G_n(x)$$$ can be simplified to

$$$F_n(x) = \frac{(x;x)_n}{(1-x)^n},$$$

and

$$$G_n(x) = \frac{(e^x;e^x)_n}{(1-e^x)^n}.$$$

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$$$?

Комментарии (3)

Написать комментарий?

Golovanov399

3 года назад, # |

+11

This seems very tempting to read, but, unfortunately, I will maybe vsolve this Petrozavodsk contests. Therefore, I'll just say that for russian-speakers there is a very good course on enumerative combinatorics in IUM: here, for example, lectures of this year, and on their website there are more materials, including pdfs from previous years. This course (called just combinatorics there), among other stuff, contains something about q-binomials, pentagonal Euler theorem, Young diagrams and so on.

→ Ответить

adamant

3 года назад, # ^ |

+14

There is also this elaborate optional course on generating functions that was taught in MIPT (also in Russian, unfortunately) by Sergey Dovgal who focuses on analytic combinatorics in his research. It gave me a very good intuition on combinatorial species and symbolic method. And it's also all in very fancy $$$\LaTeX$$$ PDFs if anyone, like me, prefers them to videos.

nor

For people who do not know Russian, a good treatment of a lot of the mentioned content can be found in Richard Stanley's Enumerative Combinatorics Vol. 1. Vol. 2 contains relevant content too.