Counting occurrences of a pattern in a binary word
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916825566019584 |
|---|---|
| author | Tian, Roger |
| author_facet | Tian, Roger |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_03205 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Counting occurrences of a pattern in a binary word Tian, Roger Combinatorics 05A05, 05A15 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. |
| title | Counting occurrences of a pattern in a binary word |
| topic | Combinatorics 05A05, 05A15 |
| url | https://arxiv.org/abs/2507.03205 |