Moment-generating functions, inversions and q-analogs

Revision en4, by adamant, 2022-02-04 21:17:40

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

or

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

  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$$$?
Tags generating function, inversions, q-analog, polynomials, tutorial, power series

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English adamant 2022-02-05 14:19:20 117 link
en7 English adamant 2022-02-04 21:29:35 1 Tiny change: '= [n+1]_x!.$$\n\nIt m' -> '= [n+1]_x!$$\n\nIt m'
en6 English adamant 2022-02-04 21:27:37 6 Tiny change: 'increases with $n-i$, wh' -> 'increases by $n-i$, wh'
en5 English adamant 2022-02-04 21:18:01 2 Tiny change: '\n\n[cut]<hr>\n\n####' -> '\n\n[cut]<br>\n\n####'
en4 English adamant 2022-02-04 21:17:40 13 Tiny change: 'x}.$$ \n\n#### M' -> 'x}.$$ \n\n[cut]\n\n#### M'
en3 English adamant 2022-02-04 21:16:58 2 typo
en2 English adamant 2022-02-04 21:09:02 4321 Tiny change: 'sions and q-analogs.' -> 'sions and $q-analogs.' (published)
en1 English adamant 2022-02-04 02:58:55 2502 Initial revision (saved to drafts)