On Cyclic Strings Avoiding a Pattern
First page number:
Last page number:
We count the number of cyclic strings over an alphabet that avoid a single pattern under two different assumptions. In the first case, we assume that the symbols of the alphabet are on numbered positions on a circle, while in the second case we assume that the symbols can be freely rotated on the circle (i.e., we deal with necklaces). In each case, we provide a generating function, and we explain how these two cases are related. For the situation of avoiding more than one pattern, we formulate a general conjecture for the first case, and a conditional result for the second case. We also explain the differences between our theory and the theory of Edlin and Zeilberger (2000) by emphasizing how we modified the definition of the enumeration of cyclic strings that avoid one or more patterns when their lengths are less than the length of the longest pattern.
Autocorrelation of a pattern; Avoiding a pattern; Cyclic string; Euler’s totient function; Generating function; Necklace
On Cyclic Strings Avoiding a Pattern.
Discrete Mathematics, 341(6),