RIFFLE SHUFFLES, CYCLES, AND DESCENTS

被引：49
作者：
DIACONIS, P
MCGRATH, M
PITMAN, J
机构：
[1] HARVARD UNIV,DEPT MATH,CAMBRIDGE,MA 02138
[2] UNIV CALIF BERKELEY,DEPT STAT,BERKELEY,CA 94720
来源：
COMBINATORICA | 1995年 / 15卷 / 01期
关键词：
Mathematics Subject Classification (1991): 05A15; 60C05;
D O I：
10.1007/BF01294457
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
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 in S-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.
引用
收藏
页码：11 / 29
页数：19
相关论文
共 21 条
  • [1] ARRATIA R, 1992, RANDOM POLYNOMIALS F
  • [2] BARBOUR A, 1991, JOINT DISTRIBUTION C
  • [3] Bayer D., 1992, ANN APPL PROBAB, V2, P294, DOI DOI 10.1214/AOAP/1177005705
  • [4] JUGGLING DROPS AND DESCENTS
    BUHLER, J
    EISENBUD, D
    GRAHAM, R
    WRIGHT, C
    [J]. AMERICAN MATHEMATICAL MONTHLY, 1994, 101 (06) : 507 - 519
  • [5] FOATA D, 1977, HIGHER COMBINATORICS
  • [6] GESSEL I, 1993, J COMB THEORY A, V64, P184
  • [7] Gilbert E, 1955, THEORY SHUFFLING
  • [8] Goncarov V., 1962, AM MATH SOC TRANSL, V19, P1
  • [9] GONCHAROV V, 1942, C R DOKLADY ACAD SCI, V35, P267
  • [10] ORDER-STATISTICS FOR DECOMPOSABLE COMBINATORIAL STRUCTURES
    HANSEN, JC
    [J]. RANDOM STRUCTURES & ALGORITHMS, 1994, 5 (04) : 517 - 533
123