A note on the distribution of the sum of lengths of the initial longest increasing sequences in cycles of random permutations
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915524967923712 |
|---|---|
| author | Mutafchiev, Ljuben |
| author_facet | Mutafchiev, Ljuben |
| contents | Let $S_n$ be the set of all permutations of $\{1,2,\ldots,n\}$ and let $σ=(σ_1,σ_2,\ldots,σ_n)\in S_n$. The {\it initial longest increasing sequence} (ILIS) in $σ$ has length $m$ if, for $1\le m\le n-1$, $σ_1<σ_2<\ldots<σ_m, σ_m>σ_{m+1}$, and has length $n$ if $σ=(1,2,\ldots,n)$. Let $l(σ)$ be the length of the ILIS in $σ$. We assume that $σ$ is represented in cycle notation, so that the first number in each cycle is the minimum number of this cycle. We also assume that $σ$ is chosen uniformly at random from $S_n$, i.e., with probability $1/n!$. Let $C_n(σ)$ be the set of all cycles of $σ$. In [9], T. Mansour investigated enumerative properties related to lengths of the ILIS in random permutations represented by the cycle notation. In particular, he studied the sum of the ILIS' lengths defined by $s_n=\sum_{c\in C_n(σ)} l(c)$ and derived exact and asymptotic expressions for its expectation and variance. In this note, we supplement Mansour's results on $s_n$ with a limit theorem. We show that $s_n$, appropriately normalized, converges weakly to a standard normal random variable as $n\to\infty$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_26129 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A note on the distribution of the sum of lengths of the initial longest increasing sequences in cycles of random permutations Mutafchiev, Ljuben Combinatorics 05A05, 60F05, 60C05 Let $S_n$ be the set of all permutations of $\{1,2,\ldots,n\}$ and let $σ=(σ_1,σ_2,\ldots,σ_n)\in S_n$. The {\it initial longest increasing sequence} (ILIS) in $σ$ has length $m$ if, for $1\le m\le n-1$, $σ_1<σ_2<\ldots<σ_m, σ_m>σ_{m+1}$, and has length $n$ if $σ=(1,2,\ldots,n)$. Let $l(σ)$ be the length of the ILIS in $σ$. We assume that $σ$ is represented in cycle notation, so that the first number in each cycle is the minimum number of this cycle. We also assume that $σ$ is chosen uniformly at random from $S_n$, i.e., with probability $1/n!$. Let $C_n(σ)$ be the set of all cycles of $σ$. In [9], T. Mansour investigated enumerative properties related to lengths of the ILIS in random permutations represented by the cycle notation. In particular, he studied the sum of the ILIS' lengths defined by $s_n=\sum_{c\in C_n(σ)} l(c)$ and derived exact and asymptotic expressions for its expectation and variance. In this note, we supplement Mansour's results on $s_n$ with a limit theorem. We show that $s_n$, appropriately normalized, converges weakly to a standard normal random variable as $n\to\infty$. |
| title | A note on the distribution of the sum of lengths of the initial longest increasing sequences in cycles of random permutations |
| topic | Combinatorics 05A05, 60F05, 60C05 |
| url | https://arxiv.org/abs/2509.26129 |