<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 5 Issue 3" %>
Generalized Riffle Shuffles and Quasisymmetric Functions
Richard P.Stanley
Department of Mathematics 2-375, Massachusetts Institute of Technology, Cambridge, MA 02139, USA
Annals of Combinatorics 5 (3) p.479-491 September, 2001
AMS Subject Classification: 05B05, 05A05, 60C05
Given a probability distribution on a totally ordered set, we define for each n>1 a related distribution on the symmetric group , called the QS-distribution. It is a generalization of the q-shuffle distribution considered by Bayer, Diaconis, and Fulman. The QS-distribution is closely related to the theory of quasisymmetric functions and symmetric functions. We obtain explicit formulas in terms of quasisymmetric and symmetric functions for the probability that a random permutation from the QS-distribution satisfies various properties, such as having a given descent set, cycle structure, or shape under the Robinson-Schensted-Knuth algorithm.
Keywords: QS-distribution, q-shuffle, quasisymmetric function, major index, RSK algorithm, increasing subsequence


1.  J. Baik, P. Deift, and K. Johansson, On the distribution of the length of the longest increasing subsequence of random permutations, J. Amer. Math. Soc. 12 (1999) 1119–1178.

2.  D. Bayer and P. Diaconis, Trailing the dovetail shuffle to its lair, Ann. Appl. Probab. 2 (1992) 294–313. In: Random Matrix Models and Their Applications, Math. Sci. Res. Inst. Publ., 40, Cambridge University Press, Cambridge, 2001, pp. 71–94.

3.  P. Bidigare, P. Hanlon, and D. Rockmore, A combinatorial description of the spectrum of the Tsetlin library and its generalization to hyperplane arrangements, Duke Math. J. 99 (1999) 135–174.

4.  Ph. Biane, Seminar talk at U.C. Berkeley, March 2000.

5.  A. Björner and M. Wachs, q-hook length formulas for forests, J. Combin. Theory Ser. A 52 (1989) 165–187.

6.  A. Borodin and A. Okounkov, A Fredholm determinant formula for Toeplitz determinants, Integral Equations and Operator Theory 37 (2000) 386–396.

7.  A. Borodin and G. Olshanski, Z-measures on partitions, Robinson-Schensted-Knuth correspondence, and b = 2 random matrix ensembles, preprint, math.CO/9905189.

8.  A. Borodin, A. Okounkov, and G. Olshanski, On asymptotics of Plancherel measures for symmetric groups, J. Amer. Math. Soc. 13 (2000) 481–515.

9.  K. Brown and P. Diaconis, Random walks and hyperplane arrangements, Ann. Probab. 26 (1998) 1813–1854.

10.  P. Diaconis, J. Fill, and J. Pitman, Analysis of top to random shuffles, Combin. Probab. Comput. 1 (1992) 135–155.

11.  P. Diaconis, M. McGrath, and J. Pitman, Riffle shuffles, cycles, and descents, Combinatorica 15 (1995) 11–29.

12.  G. Duchamp, F. Hivert, and J.-Y. Thibon, Une généralisation des fonctions quasi-symétriques et des fonctions symétriques non commutatives, C. R. Acad. Sci. Paris Sér. I Math. 328 (1999) 1113–1116.

13.  G. Duchamp, A. Klyachko, D. Krob, and J.-Y. Thibon, Noncommutative symmetric functions III: Deformations of Cauchy and convolution algebras, Discrete Math. Theoret. Comput. Sci. 1 (1997) 159–216.

14.  J. Fulman, The combinatorics of biased riffle shuffles, Combinatorica 18 (1998) 173–184.

15.  J. Fulman, Applications of symmetric functions to cycle and subsequence structure after shuffles, preprint, math.CO/0102176.

16.  A. Garsia and C. Reutenauer, A decomposition of Solomon’s descent algebra, Adv. Math. 77 (1989) 189–262.

17.  I.M. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V.S. Retakh, and J.-Y. Thibon, Noncommutative symmetric functions, Adv. Math. 112 (1995) 218–348.

18.  I. Gessel and C. Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory Ser. A 64 (1993) 189–215.

19.  C. Greene, An extension of Schensted’s theorem, Adv. Math. 14 (1974) 254–265.

20.  A.R. Its, C.A. Tracy, and H. Widom, Random words, Toeplitz determinants and integrable systems I, In: Random Matrix Models and Their Applications, Math. Sci. Res. Inst. Publ., 40, Cambridge University Press, Cambridge, 2001, pp. 245–258.

21.  K. Johansson, Discrete orthogonal polynomial ensembles and the Plancherel measure, Ann. Math. 153 (2001) 259–296.

22.  D.E. Knuth, The Art of Computer Programming, Vol. 3, Sorting and Searching, Second Ed., Addison-Wesley, Reading, Massachusetts, 1998.

23.  D. Krob, B. Leclerc, and J.-Y. Thibon, Noncommutative symmetric functions II: Tranformations of alphabets, Internat. J. Algebra Comput. 7 (1997) 181–264.

24.  G. Kuperberg, Random words, quantum statistics, central limits, random matrices, Methods Appl. Anal., to appear.

25.  B.F. Logan and L.A. Shepp, A variational problem for random Young tableaux, Adv. Math. 26 (1977) 206–222.

26.  I.G. Macdonald, Symmetric Functions and Hall Polynomials, Second Ed., Oxford University Press, Oxford, 1995.

27.  A. Okounkov, Infinite wedge and random partitions, Selecta Math. 7 (2001) 57–81.

28.  A. Okounkov, Random matrices and random permutations, Internat. Math. Res. Notices 2000 1043–1095.

29.  A. Okounkov, SL(2) and z-measures, In: Random Matrix Models and Their Applications, Math. Sci. Res. Inst. Publ., 40, Cambridge University Press, Cambridge, 2001, pp. 407–420.

30.  C. Reutenauer, Free Lie Algebras, Oxford University Press, Oxford, 1993.

31.  C.E. Schensted, Longest increasing and decreasing subsequences, Canad. Math. J. 13 (1961) 179–191.

32.  R. Stanley, Ordered structures and partitions, Mem. Amer. Math. Soc. 119 (1972).

33.  R. Stanley, Enumerative Combinatorics, Vol. 1, Second Printing, Cambridge University Press, New York/Cambridge, 1996.

34.  R. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, New York /Cambridge, 1999.

35.  A.M. Vershik and S.V. Kerov, Asymptotic behavior of the Plancherel measure of the symmetric group and the limit form of Young tableaux, Soviet Math. Dokl. 18 (1977) 527–531; translated from Dokl. Akad. Nauk SSSR 233 (1977) 1024–1027.