Asymptotic bounds for the number of closed and privileged words
The electronic journal of combinatorics, Tome 31 (2024) no. 2
A word $w$ has a border $u$ if $u$ is a non-empty proper prefix and suffix of $u$. A word $w$ is said to be closed if $w$ is of length at most $1$ or if $w$ has a border that occurs exactly twice in $w$. A word $w$ is said to be privileged if $w$ is of length at most $1$ or if $w$ has a privileged border that occurs exactly twice in $w$. Let $C_k(n)$ (resp. $P_k(n)$) be the number of length $n$ closed (resp. privileged) words over a $k$-letter alphabet. In this paper, we improve existing upper and lower bounds on $C_k(n)$ and $P_k(n)$. We completely resolve the asymptotic behaviour of $C_k(n)$. We also nearly completely resolve the asymptotic behaviour of $P_k(n)$ by giving a family of upper and lower bounds that are separated by a factor that grows arbitrarily slowly.
DOI :
10.37236/12115
Classification :
68R15, 05A05, 05A16, 94A45, 68R05
Affiliations des auteurs :
Daniel Gabrić 1
@article{10_37236_12115,
author = {Daniel Gabri\'c},
title = {Asymptotic bounds for the number of closed and privileged words},
journal = {The electronic journal of combinatorics},
year = {2024},
volume = {31},
number = {2},
doi = {10.37236/12115},
zbl = {7882966},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12115/}
}
Daniel Gabrić. Asymptotic bounds for the number of closed and privileged words. The electronic journal of combinatorics, Tome 31 (2024) no. 2. doi: 10.37236/12115
Cité par Sources :