Counting bordered and primitive words with a fixed weight

: Harju T, Nowotka D

Publisher: ELSEVIER SCIENCE BV

: 2005

: Theoretical Computer Science

: THEORETICAL COMPUTER SCIENCE

: THEOR COMPUT SCI

: 340

: 2

: 273

: 279

: 7

: 0304-3975

DOI: https://doi.org/10.1016/j.tcs.2005.03.040

A word w is primitive if it is not a proper power of another word, and w is unbordered if it has no prefix that is also a suffix of w. We study the number of primitive and unbordered words w with a fixed weight, that is, words for which the Parikh vector of w is a fixed vector. Moreover, we estimate the number of words that have a unique border. (c) 2005 Elsevier B.V All rights reserved.

Mathematics