A natural bijection for contiguous pattern avoidance in words. (English) Zbl 1530.05002
Summary: Two words \(p\) and \(q\) are avoided by the same number of length-\(n\) words, for all \(n\), precisely when \(p\) and \(q\) have the same set of border lengths. Previous proofs of this theorem use generating functions but do not provide an explicit bijection. We give a bijective proof for all pairs \(p\), \(q\) that have the same set of proper borders, establishing a natural bijection from the set of words avoiding \(p\) to the set of words avoiding \(q\).
MSC:
| 05A05 | Permutations, words, matrices |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Claesson, Anders; Kitaev, Sergey, Classification of bijections between 321- and 132-avoiding permutations. Sémin. Lothar. Comb. (2008/2009) · Zbl 1393.05010 |
| [2] | Goulden, I. P.; Jackson, D. M., An inversion theorem for cluster decompositions of sequences with distinguished subsequences. J. Lond. Math. Soc. (2), 3, 567-576 (1979) · Zbl 0467.05008 |
| [3] | Guibas, L. J.; Odlyzko, A. M., String overlaps, pattern matching, and nontransitive games. J. Comb. Theory, Ser. A, 2, 183-208 (1981) · Zbl 0454.68109 |
| [4] | Holub, Štěpán; Shallit, Jeffrey, Periods and borders of random words · Zbl 1388.68244 |
| [5] | Hang Kim, Ki; Putcha, Mohan S.; Roush, Fred W., Some combinatorial properties of free semigroups. J. Lond. Math. Soc., 3, 397-402 (1977) · Zbl 0368.20036 |
| [6] | Noonan, John; Zeilberger, Doron, The Goulden-Jackson cluster method: extensions, applications and implementations. J. Differ. Equ. Appl., 4-5, 355-377 (1999) · Zbl 0935.05003 |
| [7] | Silberger, D. M., How many unbordered words?. Comment. Math. Prace Mat., 1, 143-145 (1980) · Zbl 0531.20034 |
| [8] | Solov’ev, A. D., A combinatorial identity and its application to the problem concerning the first occurrence of a rare event. Theory Probab. Appl., 2, 276-282 (1966) · Zbl 0154.43104 |
| [9] | Zeilberger, Doron, Enumeration of words by their number of mistakes. Discrete Math., 1, 89-91 (1981) · Zbl 0461.05005 |
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.
