de Bruijn Nicolaas Govert

Imaginez un clavier composé seulement de 0 et de 1. Une suite de de Bruijn range ces symboles en cercle pour que chaque petit motif de longueur fixée apparaisse une fois, et une seule.

Pour les motifs de trois symboles, la suite circulaire 00010111 contient ainsi 000, 001, 010, 101, 011, 111, 110 et 100. Elle offre un inventaire compact de toutes les possibilités, sans répétition. Cette idée relie une règle très concrète de comptage à la combinatoire et à la théorie des graphes, domaines dans lesquels Nicolaas de Bruijn a travaillé.

Une suite de de Bruijn est une suite circulaire de symboles sur un alphabet donné, telle que toute sous-suite circulaire de longueur fixée apparaît exactement une fois. Si l’alphabet comporte k symboles et si la longueur choisie est n, la suite contient kⁿ positions, en comptant les répétitions éventuelles de symboles mais pas une position de départ privilégiée. La lecture reprend au début après le dernier symbole. Dans l’exemple binaire, l’alphabet est {0, 1} et la longueur est 3. Les huit mots possibles sont donc parcourus dans une même boucle par 00010111. Les fenêtres qui franchissent la fin, comme 110 puis 100, font partie de la définition circulaire. La propriété concerne les sous-suites consécutives, et non toutes les sous-séquences obtenues en sautant des positions. Elle s’applique à des alphabets finis et à une longueur entière positive ; le choix d’un autre alphabet ou d’une autre longueur produit une autre suite de de Bruijn.

Prenons une suite binaire circulaire et cherchons à faire apparaître chaque motif de trois symboles une seule fois. Les données sont l’alphabet {0, 1}, la longueur n = 3 et la suite candidate 00010111.

La première fenêtre est 000. En avançant d’une position, on lit 001, puis 010, puis 101, puis 011, puis 111.

En poursuivant autour du cercle, les fenêtres qui utilisent la fin puis le début sont 110 et 100. La liste obtenue est donc 000, 001, 010, 101, 011, 111, 110, 100.

Il y a 2³ = 8 motifs binaires de longueur 3, et la liste contient huit fenêtres distinctes. La candidate est donc une suite de de Bruijn pour ces paramètres. Le contrôle consiste à vérifier à la fois le nombre de fenêtres et l’absence de doublon, en incluant le passage par la fin.

En combinatoire, une suite de de Bruijn sert à énumérer des motifs consécutifs avec une longueur totale minimale. Elle convient lorsque l’ordre local des symboles est important et que chaque motif doit être rencontré sans répétition.

En théorie des graphes, on peut représenter chaque motif de longueur n − 1 par un sommet et chaque motif de longueur n par une transition. Par exemple, dans 00010111, la fenêtre 001 correspond à la transition du sommet 00 vers le sommet 01 : les deux derniers symboles de 001 reprennent les deux premiers de 01. Une recherche de circuit dans ce graphe aide alors à construire la suite circulaire. Cette représentation est préférable à une simple liste lorsque les recouvrements entre motifs doivent être suivis explicitement.

Pour vérifier une suite proposée, on fixe d’abord l’alphabet et la longueur des motifs, puis on parcourt toutes les fenêtres circulaires. Le critère observable est simple : chaque motif attendu doit apparaître une fois, sans doublon ni oubli.

Une suite de de Bruijn ne se confond pas avec une suite où chaque symbole apparaît une seule fois. Le critère porte sur les motifs consécutifs de longueur n, pas sur les symboles pris isolément. Ainsi, dans 00010111, le symbole 0 est répété, mais les huit motifs de longueur 3 restent distincts.

Elle ne se confond pas non plus avec une permutation de tous les mots de longueur n écrits les uns à la suite des autres. Dans une suite de de Bruijn, les fenêtres se recouvrent ; c’est précisément ce recouvrement qui permet de condenser les motifs dans kⁿ positions au lieu de les juxtaposer sans partage.

Le mot « sous-suite » peut induire une lecture trop large. La propriété ne vise que les symboles consécutifs, avec une longueur fixée. Si l’on autorise des sauts, le test ne mesure plus la propriété de de Bruijn et peut compter de nombreux motifs supplémentaires.

La circularité est un point charnière. Pour 00010111 et des motifs de longueur 3, les fenêtres 110 et 100 utilisent respectivement les derniers symboles puis le début. Une lecture linéaire qui s’arrête au dernier symbole ne trouve que six fenêtres et conclut à tort qu’il manque des motifs.

La longueur attendue dépend des paramètres. Avec un alphabet de k symboles et des motifs de longueur n, il faut kⁿ fenêtres circulaires. Changer l’alphabet ou n change donc le nombre de motifs à contrôler ; une suite correcte pour un cas ne l’est pas automatiquement pour un autre.

Les pavages de Penrose offrent un autre aperçu des recherches de Nicolaas de Bruijn : l’article Éblouissants pavages de Penrose permet de voir comment une méthode de construction par projection fait apparaître une organisation apériodique. Le lien prolonge la fiche vers la géométrie, sans confondre ce sujet avec les suites de de Bruijn.