Reference : Jouer avec les mots, pourquoi et comment ?
Learning materials : Course notes
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/193282
Jouer avec les mots, pourquoi et comment ?
French
Rigo, Michel mailto [Université de Liège > Département de mathématique > Mathématiques discrètes >]
2016
ULB
Notes de la huitième Brussels Summer School of Mathematics (BSSM)
[en] combinatoire ; morphisme ; Thue-Morse
[en] Ce texte reprend l'essentiel de ma présentation à la Brussels Math. Summer School du 4 août 2015. Il s'agit d'une courte introduction à la combinatoire des mots. A l'instar de Raymond Queneau et ses cent mille milliards de poèmes, nous construisons des suites aux propriétés surprenantes. Pour ne pas allonger le texte, nous avons décidé d'éviter l'emploi d'automates finis.

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.

Un carré est la juxtaposition de deux répétitions d'un même mot. On dira qu'un mot comme `taratata' contient un carré. Il est aisé de vérifier que, si on dispose uniquement de deux symboles, alors tout mot de longueur au moins 4 contient un carré. Cette observation amène de nombreuses questions 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 ?
Researchers ; Students
http://hdl.handle.net/2268/193282
https://bssm.ulb.ac.be/

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
bssm_tex.pdfAuthor preprint142.33 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.