Shuffle squares and reverse shuffle squares. (English) Zbl 07799830
Summary: Let \(\mathcal{SS}_k ( n )\) be the family of shuffle squares in \([ k ]^{2 n} \), words that can be partitioned into two disjoint identical subsequences. Let \(\mathcal{RSS}_k ( n )\) be the family of reverse shuffle squares in \([ k ]^{2 n} \), 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
\[
| \mathcal{SS}_k ( n ) | = \frac{ 1}{ n + 1} \binom{2 n}{n} k^n - \binom{2 n - 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{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 \(| \mathcal{SS}_2 ( n ) | \geq \binom{2 n}{n})\).
MSC:
| 68Rxx | Discrete mathematics in relation to computer science |
| 05Axx | Enumerative combinatorics |
| 68Qxx | Theory of computing |
Software:
OEISReferences:
| [1] | Alon, N.; Spencer, J. H., The Probabilistic Method (2016), John Wiley and Sons, Inc. · Zbl 1333.05001 |
| [2] | Axenovich, M.; Person, Y.; Puzynina, S., A regularity lemma and twins in words. J. Combin. Theory Ser. A, 733-743 (2012) · Zbl 1262.68144 |
| [3] | Bukh, B.; Hogenson, R., Length of the longest common subsequence between overlapping words. SIAM J. Discrete Math., 721-729 (2018) · Zbl 1434.60037 |
| [4] | Bukh, B.; Ma, J., Longest common subsequence in sets of words. SIAM J. Discrete Math., 2042-2049 (2014) · Zbl 1318.68132 |
| [5] | Bukh, B.; Zhou, L., Twins in words and long common subsequences in permutations. Israel J. Math., 183-209 (2013) · Zbl 1354.68213 |
| [6] | Bulteau, L.; Vialette, S., Recognizing binary shuffle squares is NP-hard. Theoret. Comput. Sci., 116-132 (2020) · Zbl 1436.68269 |
| [7] | Buss, S.; Soltys, M., Unshuffling a square is NP-hard. J. Comput. System Sci., 766-776 (2014) · Zbl 1285.68130 |
| [8] | Connolly, S.; Gabor, Z.; Godbole, A., The location of the first ascent in a 123-avoiding permutation. Integers (2015) · Zbl 1317.05011 |
| [9] | Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms, 350-355 (2001), MIT Press and McGraw-Hill · Zbl 1047.68161 |
| [10] | Deutsch, E., Dyck path enumeration. Discrete Math., 167-202 (1999) · Zbl 0932.05006 |
| [11] | Erickson, J., How hard is unshuffling a string?, https://cstheory.stackexchange.com/q/34, (https://cstheory.stackexchange.com/users/111/jeff |
| [12] | V. Guruswami, X. He, R. Li, The zero-rate threshold for adversarial bit-deletions is less than 1/2, in: FOCS’21. |
| [13] | Henshall, D.; Rampersad, N.; Shallit, J., Shuffling and unshuffling. Bull. EATCS, 131-142 (2012) · Zbl 1394.68212 |
| [14] | Hirschberg, D. S., A linear space algorithm for computing maximal common subsequences. Commun. ACM, 341-343 (1975) · Zbl 0301.68042 |
| [15] | Levenshtein, V. I., Binary codes capable of correcting deletions, insertions, and reversals. Sov. Phys. Doklady, 707-710 (1966) · Zbl 0149.15905 |
| [16] | OEIS Foundation Inc., The on-line encyclopedia of integer sequences (2021), http://oeis.org/A191755 |
| [17] | OEIS Foundation Inc., The on-line encyclopedia of integer sequences (2021), http://oeis.org/A002054 |
| [18] | R. Rizzi, S. Viallete, On recognizing words that are squares for the shuffle product, in: International Computer Science Symposium in Russia, 2013. |
| [19] | Wilf, H. S., Generatingfunctionology (1994), Academic Press: Academic Press New York · Zbl 0831.05001 |
| [20] | Xia, X., Bioinformatics and the Cell: Modern Computational Approaches in Genomics, Proteomics and Transcriptomics (2007), Springer: Springer New York · Zbl 1166.92023 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
