##
**
Improved Estimates for the Number of Privileged Words
**

###
Jeremy Nicholson and Narad Rampersad

Department of Mathematics and Statistics

University of Winnipeg

515 Portage Avenue

Winnipeg, Manitoba R3B 2E9

Canada

**Abstract:**

In combinatorics on words, a word *w* of length *n*
over an alphabet of
size *q* is said to be *privileged* if *n* ≤ 1,
or if *n* ≥ 2 and *w* has a
privileged border that occurs exactly twice in *w*. Forsyth,
Jayakumar and Shallit proved that there exist at least
2^{n-5}/*n*^{2} privileged
binary words of length *n*.
Using the work of Guibas and Odlyzko, we prove that there are
constants *c* and *n*_{0} such that for
*n* ≥ *n*_{0},
there are at least
*c**q*^{n}/(*n*(log_{q} *n*)^{2})
privileged words of length *n* over an alphabet of size *q*.
Thus, for *n* sufficiently large,
we improve the earlier bound determined by Forsyth,
Jayakumar and Shallit, and generalize it for all *q*.

**
Full version: pdf,
dvi,
ps,
latex
**

(Concerned with sequence
A231208.)

Received January 23 2018; revised version received May 2 2018.
Published in *Journal of Integer Sequences*, May 7 2018.

Return to
**Journal of Integer Sequences home page**