Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin Types A, B and D

详细信息    查看全文

• 作者：John R. Britnell^a ; ^{j.britnell@imperial.ac.uk} ; Mark Wildon^b ; ^{mark.wildon@rhul.ac.uk}
• 关键词：Bell number ; Stirling number ; Symmetric group ; Partition ; Young diagram ; Random-to-top shuffle ; Top-to-random shuffle
• 刊名：Journal of Combinatorial Theory, Series A
• 出版年：2017
• 出版时间：May 2017
• 年：2017
• 卷：148
• 期：Complete
• 页码：116-144
• 全文大小：603 K
• 卷排序：148

文摘

Let Bt(n)Bt(n) be the number of set partitions of a set of size t into at most n   parts and let Bt′(n) be the number of set partitions of {1,…,t}{1,…,t} into at most n parts such that no part contains both 1 and t or both i   and i+1i+1 for any i∈{1,…,t−1}i∈{1,…,t−1}. We give two new combinatorial interpretations of the numbers Bt(n)Bt(n) and Bt′(n) using sequences of random-to-top shuffles, and sequences of box moves on the Young diagrams of partitions. Using these ideas we obtain a very short proof of a generalization of a result of Phatarfod on the eigenvalues of the random-to-top shuffle. We also prove analogous results for random-to-top shuffles that may flip certain cards. The proofs use the Solomon descent algebras of Types A, B and D. We give generating functions and asymptotic results for all the combinatorial quantities studied in this paper.