Counting occurrences of a pattern in a binary word

Abstract

Enumerating the number of times one word occurs in another is a much-studied combinatorial subject. By utilizing a method that we call ``lexicographic extreme referencing'', we provide a formula for computing occurrences of one binary word in another. We then study $B_{n,p}(k)$, the number of binary words of length $n$ containing a given word $p$ exactly $k$ times. For this purpose, we first use lexicographic extreme referencing to provide an algorithm for constructing all words $w$ that contain a given word $p$. Afterward, we give a modified version of this algorithm for constructing the subset of binary words that are ``primitive'' with respect to $p$, and we discuss approaches for finding $B_{n,p}(k)$ via primitive words.

12 pages