Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.04136 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914179103850496 |
|---|---|
| author | Chen, William Y. C. Wang, Elena L. |
| author_facet | Chen, William Y. C. Wang, Elena L. |
| contents | This paper is concerned with a duality between $r$-regular permutations and $r$-cycle permutations, and a monotone property due to Bóna-McLennan-White on the probability $p_r(n)$ for a random permutation of $\{1,2,\ldots, n\}$ to have an $r$-th root, where $r$ is a prime. For $r=2$, the duality relates permutations with odd cycles to permutations with even cycles. To handle the general case where $r\geq 2$, we define an $r$-enriched permutation as a permutation with $r$-singular cycles colored by one of the colors $1, 2, \ldots, r-1$. In this setup, we discover a bijection between $r$-regular permutations and enriched $r$-cycle permutations, which in turn yields a stronger version of an inequality of Bóna-McLennan-White. This leads to a fully combinatorial understanding of the monotone property, thereby answering their question. When $r$ is a prime power $q^l$, we further show that $p_r(n)$ is monotone. In the case that $n+1 \not\equiv 0 \pmod q$, the equality $p_r(n)=p_r(n+1)$ has been established by Chernoff. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_04136 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Enriched Cycle Structures and Roots of Permutations Chen, William Y. C. Wang, Elena L. Combinatorics 05A05, 05A19, 05A20 This paper is concerned with a duality between $r$-regular permutations and $r$-cycle permutations, and a monotone property due to Bóna-McLennan-White on the probability $p_r(n)$ for a random permutation of $\{1,2,\ldots, n\}$ to have an $r$-th root, where $r$ is a prime. For $r=2$, the duality relates permutations with odd cycles to permutations with even cycles. To handle the general case where $r\geq 2$, we define an $r$-enriched permutation as a permutation with $r$-singular cycles colored by one of the colors $1, 2, \ldots, r-1$. In this setup, we discover a bijection between $r$-regular permutations and enriched $r$-cycle permutations, which in turn yields a stronger version of an inequality of Bóna-McLennan-White. This leads to a fully combinatorial understanding of the monotone property, thereby answering their question. When $r$ is a prime power $q^l$, we further show that $p_r(n)$ is monotone. In the case that $n+1 \not\equiv 0 \pmod q$, the equality $p_r(n)=p_r(n+1)$ has been established by Chernoff. |
| title | Enriched Cycle Structures and Roots of Permutations |
| topic | Combinatorics 05A05, 05A19, 05A20 |
| url | https://arxiv.org/abs/2502.04136 |