On Cyclic Strings Avoiding a Pattern

Document Type

Article

Publication Date

3-26-2018

Publication Title

Discrete Mathematics

Volume

341

Issue

6

First page number:

1662

Last page number:

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

Language

english

Find It

UNLV article access

Search your library

Share

COinS