Abstract
We derive closed form expressions and limiting formulae for a variety of functions of a permutation resulting from repeated riffle shuffles. The results allow new formulae and approximations for the number of permutations inS n with given cycle type and number of descents. The theorems are derived from a bijection discovered by Gessel. A self-contained proof of Gessel's result is given.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Arratia, R., Barbour, A., andTavaré, S.: On Random Polynomials over Finite Fields. Technical Report, Department of Statistics, U.S.C., 1992.
Barbour, A., andStein, C.: On the joint distribution of the cycles of random permutations, Technical report, Dept. of Statistics, Stanford University, 1991.
Bayer, D., andDiaconis, P. Trailing the dovetail shuffle to its lair.Ann. Appl. Prob.,2 (1992), 294–313.
Buhler, J., Eisenbud, D., Graham, R. L., andWright, C.: Juggling drops and descents.Amer. Math. Monthly,101 (1994), 507–519.
Foata, D.: Distributions euleriennes et mahoniennes sur le groupe des permutations. In: M. Aigner (ed.),Higher Combinatorics, Holland: Reidel, 1977.
Gessel, I., andReutenauer, C.: Counting permutations with given cycle structure and descent set.J. Combin. Theory, A 64 (1993), 184–215.
Gilbert, E.: Theory of Shuffling. Technical memorandum, Bell Laboratories, 1955.
Goncharov, V. L.: Sur la distribution des cycles dans les permutations, C. R. (Doklady).Acad. Sci. URSS (N.S) 35 (1942), 267–269.
Goncharov, V. L.: Du domaine d'analyse combinatoric.Bull. Acad. Sci. USSR Ser. Mat. (Izv. Akad. Nauk SSSR)8 (1944), 3–48,Amer. Math. Soc. Trans. (2)19 (1962), 1–46.
Hansen, J.: Order statistics for decomposable combinatorial structures.Rand. Struct. Alg. 5 (1994), 517–533.
Lidl, R., andNiederreiter, H.:Introduction to Finite Fields and their Applications, Cambridge University Press, Cambridge, 1986.
Lothaire, M.:Combinatorics on Words, Addison Wesley, Reading, Mass, 1983.
Metropolis, N. andRota, G. C.: Witt vectors and the algebra of necklaces,Adv. Math. 50 (1983), 15–125.
Metropolis, N., andRota, G. C.: The cyclotomic identity,Contemp. Math. 34 (1984), 19–27.
Reeds, J.: Theory of Shuffling. Unpublished manuscript, 1976.
Shepp, L., andLloyd, S. P.: Ordered cycle length in a random permutation,Trans. Amer. Math. Soc. 121 (1966), 340–357.
Stanley, R.:Ordered Structures and Partitions, Memoirs of The Amer. Math. Soc., Providence, R.I. 1971.
Stanley, R.:Enumerative Combinatorics, Wadsworth, Belmont CA, 1986.
Vershik, A. M., andSchmidt, A.: Limit measures arising in asymptotic theory of symmetric groups,Prob. Th. Appl. 22 (1977), 72–88,23 (1977), 34–46.
Worpitsky, J.: Studien über die Bernoullischen und Eulerschen Zahlen,Journ. für die reine und angewandte Math. 94 (1881), 103–232.