Mots de De Bruijn

Définition

Les mots de De Bruijn sont les chaînes circulaires, les plus courtes possibles, contenant tous les mots de longueur n d'un alphabet A de p lettres.
B(n, p) désigne parfois le nombre de ces mots circulaires de De Bruijn. B(n, p)= pⁿ est aussi le nombre de mots de n lettres sur l'alphabet A de p lettres.

Ces mots peuvent être, par exemple, des codes d'accès de portes d'immeubles ...

Ainsi la chaîne (circulaire) de longueur 3²=9, 'aaccbcabb' contient tous les mots de 2 lettres différentes ou non de l'alphabet {a, b, c}.
Le mot 'ba' s'obtient en complétant la chaîne par son début : aaccbcab'ba'accbcabb.

Recherche

Compléments
Petits morceaux de musique MIDI dont les airs sont des chaînes de Debruijn a3-10.mid (les assemblages de 3 notes parmi 10), a4-6.mid, a5-4.mid
Mots de de Bruijn Plusieurs solutions, recherche de circuit hamiltonien
debruijn.c Programme en C de recherche des mots de de Bruijn
Pages de liens sur les mathématiques, les mots et les chaînes, les polynômes cyclotomiques, la combinatoire

Liens

Le De Bruijn B(d,n) Maîtrise Informatique - Université de Bretagne Occidentale

de Bruijn Sequence MathWorld

String MathWorld

Solution to the /combinatorics/full problem

Pour un premier contact, écrivez-moi en utilisant ce formulaire.
Les correspondances suivantes pourront se faire par messagerie électronique.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès maintenant et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige votre travail ou le corrige de cette communication et lui montrer les documents fournis.