Autocorrelation and the Enumeration of Strings Avoiding a Fixed String
Kimmo Eriksson · Combinatorics Probability Computing · 1997
Considering strings over a finite alphabet [Ascr ], say that a string is w-avoiding if it does not contain w as a substring. It is known that the number aw(n) of w-avoiding strings of length n depends only on the autocorrelation of w as defined by Guibas–Odlyzko. We give a simple criterion on the autocorrelations of w and w′ for determining whether aw(n) > aw′(n) for all large enough n.