Counting bordered and primitive words with a fixed weight

详细信息    查看全文

• 作者：Harju ; Tero ; Nowotka ; Dirk
• 关键词：Combinatorics on words ; Borders ; Primitive words ; Mö ; bius function
• 刊名：Theoretical Computer Science
• 出版年：2005
• 出版时间：June 27, 2005
• 年：2005
• 卷：340
• 期：2
• 页码：273-279
• 全文大小：173 K

文摘

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.