Browse issues
no. 5
Permutations with restricted cycle lengths
Bóna, Miklós1; Pittel, Boris2
1 University of Florida Dept. of Mathematics 1400 Stadium Rd. Gainesville, FL 32611-8105 (USA)
2 The Ohio State University Department of Mathematics Columbus, OH 43210, USA
Algebraic Combinatorics, Volume 8 (2025) no. 5, pp. 1233-1249

We find exact and asymptotic formulas for the number of pairs $(s,z)$ of $N$-cycles $s$ and $z$ such that all cycles of the product $s\cdot z$ have lengths from a given set of integers. We then apply one of these results to prove a surprisingly high lower bound for the number of permutations whose block transposition distance from the identity is at least $(N+1)/2$.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.449
Classification: 60C05, 05C05, 92B10
Keywords: permutations, cycles, sorting, conjugacy classes

Bóna, Miklós 1; Pittel, Boris 2

1 University of Florida Dept. of Mathematics 1400 Stadium Rd. Gainesville, FL 32611-8105 (USA)
2 The Ohio State University Department of Mathematics Columbus, OH 43210, USA
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2025__8_5_1233_0,
     author = {B\'ona, Mikl\'os and Pittel, Boris},
     title = {Permutations with restricted cycle lengths},
     journal = {Algebraic Combinatorics},
     pages = {1233--1249},
     year = {2025},
     publisher = {The Combinatorics Consortium},
     volume = {8},
     number = {5},
     doi = {10.5802/alco.449},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.449/}
}
TY  - JOUR
AU  - Bóna, Miklós
AU  - Pittel, Boris
TI  - Permutations with restricted cycle lengths
JO  - Algebraic Combinatorics
PY  - 2025
SP  - 1233
EP  - 1249
VL  - 8
IS  - 5
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.449/
DO  - 10.5802/alco.449
LA  - en
ID  - ALCO_2025__8_5_1233_0
ER  - 
%0 Journal Article
%A Bóna, Miklós
%A Pittel, Boris
%T Permutations with restricted cycle lengths
%J Algebraic Combinatorics
%D 2025
%P 1233-1249
%V 8
%N 5
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.449/
%R 10.5802/alco.449
%G en
%F ALCO_2025__8_5_1233_0
Bóna, Miklós; Pittel, Boris. Permutations with restricted cycle lengths. Algebraic Combinatorics, Volume 8 (2025) no. 5, pp. 1233-1249. doi: 10.5802/alco.449

[1] Bafna, Vineet; Pevzner, Pavel A. Sorting by transpositions, SIAM J. Discrete Math., Volume 11 (1998) no. 2, pp. 224-240 | Zbl | DOI | MR

[2] Boccara, G. Nombre de représentations d’une permutation comme produit de deux cycles de longueurs données, Discrete Math., Volume 29 (1980) no. 2, pp. 105-134 | Zbl | DOI | MR

[3] Bóna, Miklós Combinatorics of permutations, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2022, xix+507 pages | Zbl | DOI | MR

[4] Bóna, Miklós; Pittel, Boris On the cycle structure of the product of random maximal cycles, Sém. Lothar. Combin., Volume 80 ([2019–2021]), Paper no. B30b, 37 pages | MR

[5] Charalambides, Charalambos A. Enumerative combinatorics, CRC Press Series on Discrete Mathematics and its Applications, Chapman & Hall/CRC, Boca Raton, FL, 2002, xvi+609 pages | Zbl | MR

[6] Christie, David A. Sorting permutations by block-interchanges, Inform. Process. Lett., Volume 60 (1996) no. 4, pp. 165-169 | Zbl | DOI | MR

[7] Cranston, Daniel W.; Sudborough, I. Hal; West, Douglas B. Short proofs for cut-and-paste sorting of permutations, Discrete Math., Volume 307 (2007) no. 22, pp. 2866-2870 | Zbl | DOI | MR

[8] Elias, Isaac; Hartman, Tzvika A 1.375-approximation algorithm for sorting by transpositions, Algorithms in bioinformatics (Lecture Notes in Comput. Sci.), Volume 3692, Springer, Berlin, 2005, pp. 204-215 | DOI | MR

[9] Eriksson, Henrik; Eriksson, Kimmo; Karlander, Johan; Svensson, Lars; Wästlund, Johan Sorting a bridge hand, Discrete Math., Volume 241 (2001) no. 1-3, pp. 289-300 | Zbl | DOI | MR

[10] Macdonald, I. G. Symmetric functions and Hall polynomials, Oxford Classic Texts in the Physical Sciences, The Clarendon Press, Oxford University Press, New York, 2015, xii+475 pages | MR

[11] Pittel, Boris Another proof of the Harer-Zagier formula, Electron. J. Combin., Volume 23 (2016) no. 1, Paper no. 1.21, 11 pages | Zbl | DOI | MR

[12] Sachkov, Vladimir N. Probabilistic methods in combinatorial analysis, Encyclopedia of Mathematics and its Applications, 56, Cambridge University Press, Cambridge, 1997, x+246 pages (translated from the Russian) | Zbl | DOI | MR

[13] Sagan, Bruce E. The symmetric group: representations, combinatorial algorithms, and symmetric functions, Graduate Texts in Mathematics, 203, Springer-Verlag, New York, 2001, xvi+238 pages | Zbl | DOI | MR

[14] Stanley, Richard P. Permutations with no runs of length 2, Space Programs Summary, Volume 37-40-4, California Institute of Technology, Pasadena, California, 1966, pp. 208-214

[15] Stanley, Richard P. Two enumerative results on cycles of permutations, European J. Combin., Volume 32 (2011) no. 6, pp. 937-943 | Zbl | DOI | MR

[16] Stanley, Richard P. Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, 208, Cambridge University Press, Cambridge, 2024, xvi+783 pages | MR

[17] Zagier, Don On the distribution of the number of cycles of elements in symmetric groups, Nieuw Arch. Wisk. (4), Volume 13 (1995) no. 3, pp. 489-495 | Zbl | MR

Cited by Sources: