En combinatoire, et notamment en combinatoire des mots, le calcul du nombre de carrés distincts que peut contenir un mot donné est un problème posé par Fraenkel et Simpson en 1998 et pas encore entièrement résolu.
Définitions Un carré est un mot de la forme , comme bonbon. Un mot est un facteur d'un mot s'il apparaît dans le mot comme une séquence consécutive de symboles ; ainsi kipé est un facteur de wikipédia.
Nombre de facteurs carrés Soit le nombre maximum de carrés distincts qui sont facteurs d'un mot de longueur . ont montré que . Ils ont conjecturé que . a donné la borne ; Nguyen Huong LamDans un rapport technique AdvOL-Report 2 (2013) a amélioré la borne à ; et obtiennent la borne ; enfin obtient . Dans , il est montré que, sur un alphabet à lettres, on a . Ceci démontre la conjecture de Fraenkel et Simpson et en fait une version plus forte.
Le nombre de puissances contenues dans un mot a été encadré par qui donne la majoration et la minoration . Il montre aussi que le nombre de toutes les puissances distinctes d’exposant au moins 2 est au plus . Une version plus récente est . Les deux textes font suite à l'article de .
Références
Bibliographie . . . .
. . .
Catégorie:Combinatoire des mots