Bell numbers and a card shuffle

Question

A deck of n cards may be 'shuffled' by moving the top card to any (random) position in the deck, and performing this operation n times. Martin Gardner asserts (Scientific American, May 1978) that the number of such shuffles that return the deck to its original state is equal to the nth Bell number. This appears to be true for the first few cases but I have not been able to explain why it should be so for all n. A set partition that corresponds to the problem seems hard to find. Symmetric groups offer some insights but nothing conclusive, so far.

Answer 1

It is slightly more convenient to consider the shuffles "played backwards", with each move taking an arbitrary card to the top of the deck. Then we're still counting shuffles (call them neutral) that leave the deck in its initial state when played.

Let's label the cards by (elements of) $[n]:=\{1,\ldots,n\}$, and let the initial state of the deck be $(1,\ldots,n)$. Then any (not only neutral) shuffle is uniquely determined by $\ell=(\ell_1,\ldots,\ell_n)$, where $\ell_k$ is (the label of) the card that is moved to the top at step $k$.

Now, to each neutral shuffle, we assign the partition of $[n]$ into the equivalence classes of the relation $j\sim k\iff\ell_j=\ell_k$. This is reversed as follows: let $[n]=N_1\cup\ldots\cup N_m$ be a partition of $[n]$, with $N_1,\ldots,N_m$ ordered so that $j\mapsto\max N_j$ is decreasing; then, we set $\ell_k=j$ iff $k\in N_j$.

The order of $N_j$ ensures that the latter gives a neutral shuffle (in the resulting deck, the card $1$ will be on top because it is moved last, and so on upto the card $m$; the remaining cards (if any) are not used, so these go to the bottom, with their order unchanged). It is also clear that different partitions map to different $\ell$'s.