Asymptotic properties of the number of inversions in a random forest

V. A. Vatutin

Matematičeskie voprosy kriptografii, Tome 11 (2020), pp. 7-22

Résumé

Let $\mathcal{F}_{n,N}=\left\{F_{n,N}\right\} $ be the set of all forests each of which is generated by $N$ labelled rooted trees $T_{1},T_{2},\ldots ,T_{N}$ having in total $n+N$ vertices (including the roots) with different labels (numbers from $1$ to $n+N$). Denote by $\lambda (u)$ the label assigned to the vertex $u$ of the forest $F_{n,N}$. We say that a vertex $u\in T_{i}$ is an ancestor of a vertex $v\in T_{i}$ and write $u\prec v$, if the path leading from the root of the tree to the vertex $v$ passes the vertex $u$. The number of inversions of a forest $F_{n,N}$ is the number of pairs of vertices $u,v$ in this forest such that $u\prec v$ and $\lambda(u)>\lambda(v)$. Assuming that $F_{n,N}$ is a forest selected randomly and equiprobably from $\mathcal{F}_{n,N}$ we find the limiting distribution of the random variable $n^{-3/2}\mathcal{l}(F_{n,N})$ as $n\rightarrow \infty $ and $2Nn^{-1/2}\rightarrow l\in \lbrack 0,\infty )$.