Affine shuffles, shuffles with cuts, the Whitehouse module, and patience sorting

JOURNAL OF ALGEBRA

卷:231

Article

Fulman, J

关键词: card shuffling;    conjugacy class;    sorting;    random matrix;    cycle structure;   

DOI  :  10.1006/jabr.2000.8339

来源: Elsevier

【 摘 要 】

Type A affine shuffles are compared with riffle shuffles followed by a cut. Although these probability measures on the symmetric group S-n are different, they both satisfy a convolution property. Strong evidence is given that when the underlying parameter q satisfies gcd(n,q - 1) = 1, the induced measures on conjugacy classes of the symmetric group coincide. This gives rise to interesting combinatorics concerning the modular equidistribution by major index of permutations in a given conjugacy class and with a given number of cyclic descents. Using representation theoretic work on the Whitehouse module, a formula is obtained for the cycle structure of a riffle shuffle followed by a cut. It is proved that the use of cuts does not speed up the convergence rate of riffle shuffles to randomness. Generating functions for the first pile size in patience sorting from decks with repeated values are derived. This relates to random matrices. (C) 2000 Academic Press.

【 授权许可】

Free