×

The average number of block interchanges needed to sort a permutation and a recent result of Stanley. (English) Zbl 1202.68272

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\).

MSC:

68R05 Combinatorics in computer science
PDFBibTeX XMLCite
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.