Shuffle Squares and Reverse Shuffle Squares

Abstract

Let ${\mathcal{SS}}_k(n)$ be the family of {\it shuffle squares} in $[k{]}^{2n}$, words that can be partitioned into two disjoint identical subsequences. Let ${\mathcal{R}\mathcal{SS}}_k(n)$ be the family of {\it reverse shuffle squares} in $[k{]}^{2n}$, 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 ${\mathcal{SS}}_k(n)$ and ${\mathcal{R}\mathcal{SS}}_k(n)$ based on numerical evidence. We prove that \[ \lvert \mathcal{SS}_k(n) \rvert=\dfrac{1}{n+1}\dbinom{2n}{n}k^n-\dbinom{2n-1}{n+1}k^{n-1}+O_n(k^{n-2}), \] confirming their conjecture for ${\mathcal{SS}}_k(n)$. We also prove a similar asymptotic formula for reverse shuffle squares that disproves their conjecture for $|{\mathcal{R}\mathcal{SS}}_k(n)|$. As these asymptotic formulas are vacuously true when the alphabet size is small, we study the binary case separately and prove that $|{\mathcal{SS}}_2(n)|\ge \left(\genfrac{}{}{0ex}{}{2n}{n}\right)$.

16 pp

References in corpus (1)

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