Skip to main navigation Skip to search Skip to main content

An upper bound of the number of distinct powers in binary words

Research output: Contribution to journalArticlepeer-review

Abstract

Let u be a finite word and r be a positive integer, a power is a word of the form uu…u︸rtimes. Particularly, a square is a word of the form uu. Fraenkel and Simpson conjectured in 1998 that the number of distinct squares in a word is bounded by its length. This conjecture was proved recently by Brlek and Li. Besides, a stronger upper bound for binary words was conjectured by Jonoska, Manea and Seki by stating that, for a word of length n over the alphabet {a,b}, if k is the least of the number of a's and the number of b's and k≥2, then the number of distinct squares is upper bounded by [Formula presented]. In this article, we prove this conjecture by giving a stronger statement on the number of distinct powers in a binary word.

Original languageEnglish
Article number113902
JournalDiscrete Mathematics
Volume347
Issue number4
DOIs
StatePublished - Apr 2024
Externally publishedYes

Keywords

  • Binary words
  • Combinatorics on words
  • Square factors

Fingerprint

Dive into the research topics of 'An upper bound of the number of distinct powers in binary words'. Together they form a unique fingerprint.

Cite this