Generalizations of an expansion formula for top to random shuffles

DOI10.1007/S00026-016-0332-YMaRDI QIDQ505704zbMATH OpenOpenAlexFDO

Authors Roger Tian

Publication date 26 January 2017

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.6900

zbMATH Keywords

group algebrapermutationsset partitionsStirling numbers of the second kindtop to random shuffles

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Partitions of sets (05A18) Combinatorial identities, bijective combinatorics (05A19)

Abstract: In the top to random shuffle, the first a cards are removed from a deck of n cards 12 cdots n and then inserted back into the deck. This action can be studied by treating the top to random shuffle as an element B_a, which we define formally in Section 2, of the algebra Q[S_n]. For a = 1, Adriano Garsia in "On the Powers of Top to Random Shuffling" (2002) derived an expansion formula for B_1^k for k leq n, though his proof for the formula was non-bijective. We prove, bijectively, an expansion formula for the arbitrary finite product B_{a_1}B_{a_2} cdots B_{a_k} where a_1, ldots, a_k are positive integers, from which an improved version of Garsia's aforementioned formula follows. We show some applications of this formula for B_{a_1}B_{a_2} cdots B_{a_k}, which include enumeration and calculating probabilities. Then for an arbitrary group G we define the group of G-permutations S_n^G := G wr S_n and further generalize the aforementioned expansion formula to the algebra Q[S_n^G] for the case of finite G, and we show how other similar expansion formulae in Q[S_n] can be generalized to Q[S_n^G].

Recommendations

• Analysis of Top To Random Shuffles
• Riffle shuffles, cycles, and descents
• Determinantal formula for generalized riffle shuffle
• Random shuffles and group representations
• Trailing the dovetail shuffle to its lair

Cites work

• A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
• A decomposition of Solomon's descent algebra
• An exact formula for the move-to-front rule for self-organizing lists
• Analysis of Top To Random Shuffles
• Combinatorial Markov chains on linear extensions
• Promotion and evacuation
• Quelques remarques sur une Construction de Schensted.
• Semigroups, rings, and Markov chains
• The stationary distribution of an interesting Markov chain

Cited in

(8)

• Total variation cutoff for the transpose top-2 with random shuffle
• Determinantal formula for generalized riffle shuffle
• Analysis of top to bottom-\(k\) shuffles
• Analysis of Top To Random Shuffles
• Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin types A, B and D
• Invariant theory for the free left-regular band and a \(q\)-analogue
• Top to random shuffles on colored permutations
• Invariant theory for the free left-regular band and a q-analogue

This page was built for publication: Generalizations of an expansion formula for top to random shuffles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q505704)