Abstract :
[fr] A l'instar de Raymond Queneau et ses cent mille milliards de poèmes, cet exposé a pour but de compter et de construire des mots aux propriétés parfois surprenantes. Les premiers résultats en combinatoire des mots remontent au début du siècle précédent, avec les travaux du mathématicien norvégien Axel Thue. Cette branche des mathématiques étudie la structure et les arrangements apparaissant au sein de suites finies, ou infinies, de symboles appartenant à un ensemble fini.
Donnons un exemple rudimentaire. Un carré est la juxtaposition de deux répétitions d'un mot, ainsi "coco" ou "bonbon" sont des carrés. On dira alors qu'un mot comme "taratata" contient un carré. Il est aisé de vérifier que, si on dispose uniquement de deux symboles "a" et "b", alors tout mot de longueur au moins 4 contient un des carrés "aa", "bb", "abab" ou encore "baba". On dira donc que, sur deux symboles, les carrés sont inévitables.
Cette observation pose des questions intéressantes et simples à formuler : Avec trois symboles, peut-on construire un mot arbitrairement long ne contenant pas de carré ? Si on se limite à deux symboles, peut-on construire un mot arbitrairement long sans cube, i.e., évitant la juxtaposition de trois répétitions d'un même mot ? En fonction de la taille de l'alphabet, quels motifs doivent nécessairement apparaître et quels sont ceux qui sont évitables ? Que se passe-t-il si on autorise certaines permutations ? etc.
Dans cet exposé, on passera en revue quelques constructions simples de mots finis ou infinis : mot de Thue-Morse, mot de Fibonacci, mots Sturmiens. Nous montrerons aussi que les applications sont nombreuses : arithmétique, transcendance en théorie des nombres, informatique mathématique et théorie des automates, pavages du plan, dynamique symbolique et codage de rotations, infographie, géométrie discrète et représentation de segment de droites à l'écran, bio-informatique, ...
