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

摘要

Let B-t(n) be the number of set partitions of a set of size t into at most n parts and let B-t(')(n) be the number of set partitions of {1,...,t} into at most n parts such that no part contains both 1 and t or both i and i + 1 for any i is an element of {1,...,t - 1}. We give two new combinatorial interpretations of the numbers Bt(n) and B-t(')(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. (C) 2016 Elsevier Inc. All rights reserved.