Shuffle Squares and Reverse Shuffle Squares

2021/09/25 by Xiaoyu He, He, Xiaoyu, Emily Huang +5
Computer Science · #Algorithms and Data Compression #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2109.12455

openalex publication_date 2021/09/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let SS_k(n) be the family of \it shuffle squares in [k]²ⁿ, words that can be partitioned into two disjoint identical subsequences. Let RSS_k(n) be the family of \it reverse shuffle squares in [k]²ⁿ, words that can be partitioned into two disjoint subsequences which are reverses of each other. Henshall, Rampersad, and Shallit conjectured asymptotic formulas for the sizes of SS_k(n) and RSS_k(n) based on numerical evidence. We prove that | SS_k(n) |=\dfrac1n+1\dbinom2nnkⁿ-\dbinom2n-1n+1k^n-1+O_n(k^n-2), confirming their conjecture for SS_k(n). We also prove a similar asymptotic formula for reverse shuffle squares that disproves their conjecture for | RSS_k(n) |. As these asymptotic formulas are vacuously true when the alphabet size is small, we study the binary case separately and prove that |SS₂(n)| ≥ \binom2nn.

Citations

• The zero-rate threshold for adversarial bit-deletions is less than 1/2

Related

• Asymptotically half of binary words are shuffle squares
• Variations on shuffle squares
• Shuffle squares and ordered nest-free graphs
• A refinement of the Shuffle Conjecture with cars of two sizes and t=1/q
• Shuffle Invariance of the Super-RSK Algorithm