The inversion statistic in derangements and in other permutations with a prescribed number of fixed points
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910927618572288 |
|---|---|
| author | Pinsky, Ross G. |
| author_facet | Pinsky, Ross G. |
| contents | We study how the inversion statistic is influenced by fixed points in a permutation. %The expected number of inversions in a uniformly random permutation in $S_n$ is $\frac{n(n-1)}4$. For each $n\in\mathbb{N}$, and each $k\in\{0,1,\cdots, n\}$, let $P_n^{(k)}$ denote the uniform probability measure on the set of permutations in $S_n$ with exactly $k$ fixed points. We obtain an exact formula for the expected number of inversions under the measure $P_n^{(k)}$ as well as for $P_n^{(k)}(σ^{-1}_i<σ^{-1}_j)$, for $1\le i<j\le n$, the $P_n^{(k)}$-probability that the number $i$ precedes the number $j$. In particular,
up to a super-exponentially small correction as $n\to\infty$, the expected number of inversions in a random derangement $(k=0)$ is $\frac16n+\frac1{12}$ more than
the value $\frac{n(n-1)}4$ that one obtains for a uniformly random
general permutation in $S_n$. On the other hand, up to a super-exponentially small correction, for $k\ge2$, the expected number of inversions in a random permutation with $k$ fixed points is $\frac{k-1}6n+\frac{k^2-k-1}{12}$ less than $\frac{n(n-1)}4$. In the borderline case, $k=1$, up to a super-exponentially small correction, the expected number of inversions in a random permutation with one fixed point is $\frac1{12}$ more than $\frac{n(n-1)}4$. The proofs make strategic and perhaps novel use of the Chinese restaurant construction for a uniformly random permutation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_02058 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The inversion statistic in derangements and in other permutations with a prescribed number of fixed points Pinsky, Ross G. Probability Combinatorics 60C05, 05A05 We study how the inversion statistic is influenced by fixed points in a permutation. %The expected number of inversions in a uniformly random permutation in $S_n$ is $\frac{n(n-1)}4$. For each $n\in\mathbb{N}$, and each $k\in\{0,1,\cdots, n\}$, let $P_n^{(k)}$ denote the uniform probability measure on the set of permutations in $S_n$ with exactly $k$ fixed points. We obtain an exact formula for the expected number of inversions under the measure $P_n^{(k)}$ as well as for $P_n^{(k)}(σ^{-1}_i<σ^{-1}_j)$, for $1\le i<j\le n$, the $P_n^{(k)}$-probability that the number $i$ precedes the number $j$. In particular, up to a super-exponentially small correction as $n\to\infty$, the expected number of inversions in a random derangement $(k=0)$ is $\frac16n+\frac1{12}$ more than the value $\frac{n(n-1)}4$ that one obtains for a uniformly random general permutation in $S_n$. On the other hand, up to a super-exponentially small correction, for $k\ge2$, the expected number of inversions in a random permutation with $k$ fixed points is $\frac{k-1}6n+\frac{k^2-k-1}{12}$ less than $\frac{n(n-1)}4$. In the borderline case, $k=1$, up to a super-exponentially small correction, the expected number of inversions in a random permutation with one fixed point is $\frac1{12}$ more than $\frac{n(n-1)}4$. The proofs make strategic and perhaps novel use of the Chinese restaurant construction for a uniformly random permutation. |
| title | The inversion statistic in derangements and in other permutations with a prescribed number of fixed points |
| topic | Probability Combinatorics 60C05, 05A05 |
| url | https://arxiv.org/abs/2505.02058 |