2020/09/30 by Samuel Johnson, Lakshman Manny, Cornelia A. Van Cott +2
Computer Science · Engineering · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Arithmetic #Combinatorics #Computer science #Deck #Discrete mathematics #Group (periodic table) #Interlacing #Mathematics #Permutation (music) #Permutation group #Physics #Shuffling #Statistics #graph theory and CDMA systems #math.CO #math.GR #msc:20B35
paper · pdf · doi:10.2140/involve.2021.14.813
published as Involve 14 (2021) 813-828 · 13 pages, 5 figures. Shortened argument in proofs of the main results, results unchanged
arxiv created 2020/10/10 · openalex publication_date 2021/12/31 · arxiv updated 2022/03/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Standard perfect shuffles involve splitting a deck of 2n cards into two stacks and interlacing the cards from the stacks. There are two ways that this interlacing can be done, commonly referred to as an in shuffle and an out shuffle, respectively. In 1983, Diaconis, Graham, and Kantor determined the permutation group generated by in and out shuffles on a deck of 2n cards for all n. Diaconis et al. concluded their work by asking whether similar results can be found for so-called generalized perfect shuffles. For these new shuffles, we split a deck of mn cards into m stacks and similarly interlace the cards with an in m-shuffle or out m-shuffle (denoted Im and Om, respectively). In this paper, we find the structure of the group generated by these two shuffles for a deck of mk cards, together with my-shuffles, for all possible values of m, k, and y. The group structure is completely determined by k/gcd(y,k) and the parity of y/gcd(y,k). In particular, the group structure is independent of the value of m.