Bóna, Miklós; Flynn, Ryan The average number of block interchanges needed to sort a permutation and a recent result of Stanley. (English) Zbl 1202.68272 Inf. Process. Lett. 109, No. 16, 927-931 (2009). Summary: We use an interesting recent result of probabilistic flavor concerning the product of two permutations consisting of one cycle each to find an explicit formula for the average number of block interchanges needed to sort a permutation of length \(n\). Cited in 8 Documents MSC: 68R05 Combinatorics in computer science Keywords:analysis of algorithms; block interchanges; permutations; sorting; cycles; probability PDFBibTeX XMLCite \textit{M. Bóna} and \textit{R. Flynn}, Inf. Process. Lett. 109, No. 16, 927--931 (2009; Zbl 1202.68272) Full Text: DOI arXiv References: [1] Boccara, G., Nombres de répresentations d’une permutation comme produit de deux cycles de longueur données, Discrete Math., 29, 105-134 (1980) · Zbl 0444.20003 [2] Bóna, M., Introduction to Enumerative Combinatorics (2007), McGraw-Hill · Zbl 1208.05001 [3] Christie, D. A., Sorting permutations by block interchanges, Inform. Process. Lett., 60, 165-169 (1996) · Zbl 0900.68232 [4] Doignon, J.-P.; Labarre, A., On Hultman numbers, Journal of Integer Sequences, 10 (2007), Article 07.6.2 · Zbl 1138.05301 [5] A. Hultman, Toric Permutations, Master’s thesis, Department of Mathematics, KTH, Stockholm, Sweden, 1999; A. Hultman, Toric Permutations, Master’s thesis, Department of Mathematics, KTH, Stockholm, Sweden, 1999 [6] Sagan, B. E., Inductive and injective proofs of log concavity results, Discrete Math., 68, 2-3, 281-292 (1988) · Zbl 0658.05003 [7] R. Stanley, Two enumerative results on cycles of permutations, preprint; R. Stanley, Two enumerative results on cycles of permutations, preprint · Zbl 1238.05015 [8] R. Stanley, Personal communication, October, 2008; R. Stanley, Personal communication, October, 2008 [9] Stanley, R., Enumerative Combinatorics, vol. 2 (1999), Cambridge University Press, (Supplementary Exercises (without solutions) for Ch. 7 (Symmetric functions)); Internet resource available at · Zbl 0928.05001 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.