Journal of Integer Sequences, Vol. 21 (2018), Article 18.3.8

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


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 2n-5/n2 privileged binary words of length n. Using the work of Guibas and Odlyzko, we prove that there are constants c and n0 such that for nn0, there are at least cqn/(n(logq 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