{
  "id": "2206.14273",
  "version": "v1",
  "published": "2022-06-28T20:04:24.000Z",
  "updated": "2022-06-28T20:04:24.000Z",
  "title": "Asymptotic bounds for the number of closed and privileged words",
  "authors": [
    "Daniel Gabric"
  ],
  "categories": [
    "math.CO",
    "cs.DM",
    "cs.FL"
  ],
  "abstract": "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 \\emph{closed} if $|w| \\leq 1$ or if $w$ has a border that occurs exactly twice in $w$. A word $w$ is said to be \\emph{privileged} if $|w| \\leq 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 prove that $C_k(n) \\in \\Theta(\\frac{k^n}{n})$. Let $\\log_k^{\\circ 0}(n) = n$ and $\\log_k^{\\circ j}(n) = \\log_k(\\log_k^{\\circ j-1}(n))$ for $j\\geq 1$. We also prove that for all $j\\geq 0$ there exist constants $N_j$, $c_j$, and $c_j'$ such that \\[c_j\\frac{k^n}{n\\log_k^{\\circ j}(n)\\prod_{i=1}^j\\log_k^{\\circ i}(n)}\\leq P_k(n) \\leq c_j'\\frac{k^n}{n\\prod_{i=1}^j\\log_k^{\\circ i}(n)}\\] for all $n>N_j$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-06-28T20:04:24.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "asymptotic bounds",
      "privileged words",
      "occurs exactly twice",
      "non-empty proper prefix",
      "letter alphabet"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}