# On Cyclic Strings Avoiding a Pattern

Article

3-26-2018

## Publication Title

Discrete Mathematics

341

6

1662

1674

## Abstract

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.

## Keywords

Autocorrelation of a pattern; Avoiding a pattern; Cyclic string; Euler’s totient function; Generating function; Necklace

## Disciplines

Applied Mathematics

english

COinS