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

Abstract

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^{\prime }(n)$ be the number of set partitions of $\{1,\dots ,t\}$ into at most $n$ parts such that no part contains both $1$ and~$t$ or both $i$ and $i+1$ for any $i\in \{1,\dots ,t-1\}$. We give two new combinatorial interpretations of the numbers $B_t(n)$ and $B_t^{\prime }(n)$ using sequences of random-to-top shuffles, %that leave a deck of cards invariant, 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.

arXiv comment25 pages