Shuffle squares and reverse shuffle squares

DOI10.1016/J.EJC.2023.103883MaRDI QIDQ6189690zbMATH OpenFDO

Authors Xiaoyu He, Emily Huang, Ihyun Nam, Rishubh Thaper

Publication date 5 February 2024

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

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

Mathematics Subject Classification ID

Enumerative combinatorics (05Axx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)

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{RSS}_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{RSS}_k(n)$ based on numerical evidence. We prove that [ lvert mathcal{SS}_k(n) vert=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 $lvertmathcal{RSS}_k(n)vert$. As these asymptotic formulas are vacuously true when the alphabet size is small, we study the binary case separately and prove that $$.

Cites work

• A linear space algorithm for computing maximal common subsequences
• A regularity lemma and twins in words
• Bioinformatics and the Cell
• Dyck path enumeration
• scientific article; zbMATH DE number 729555 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• Introduction to algorithms
• Length of the longest common subsequence between overlapping words
• Longest common subsequences in sets of words
• Recognizing binary shuffle squares is \textsf{NP}-hard
• Shuffling and unshuffling
• The location of the first ascent in a 123-avoiding permutation
• The probabilistic method
• Twins in words and long common subsequences in permutations
• Unshuffling a square is NP-hard

Cited in

(2)

• Shuffle squares and nest-free graphs
• How far are ternary words from shuffle squares?

This page was built for publication: Shuffle squares and reverse shuffle squares

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