Collier (combinatoire)

Les deux premiers de ces colliers sont apériodiques, le troisième ne l'est pas.

Un collier apériodique est la classe d'équivalence de suites dont deux rotations non triviales ne sont jamais égales. Il est équivalent de dire qu'un collier apériodique est la classe d'un mot primitif, c'est-à-dire d'un mot qui n'est pas puissance d'un autre mot. L'exemple du début, qui correspond au mot ABCBAAC, est une collier primitif.

Le nombre de colliers apériodiques de longueur n sur un alphabet à k lettres est

${\displaystyle M_{k}(n)={1 \over n}\sum _{d\mid n}\mu (d)k^{n/d}}$.

Ici, ${\displaystyle \mu }$ est la fonction de Möbius. Les fonctions ${\displaystyle M_{k}(n)}$ sont aussi appelés les polynômes de colliers (en la variable ${\displaystyle k}$), et la formule ci-dessus est attribuée au colonel Moreau. En fait, Moreau ne compte pas les colliers apériodiques, mais les colliers tout court, et même les colliers contenant une certaine répartition du nombre de perles de chaque couleur, ce qui rend sa formule moins limpide.

Pour ${\displaystyle k=2}$, la suite des ${\displaystyle M_{k}(n)}$ est la suite A001037 de l'OEIS. Pour ${\displaystyle n=3}$ et ${\displaystyle n=4}$, les colliers apériodiques binaires sont 001,011 et 0001,0011,0111.

La formule ci-dessus est dérivée de l'expression

${\displaystyle k^{n}=\sum _{d\,|\,n}d\,M_{k}(d)}$

et s'obtient par inversion de Möbius.

Pour établir la formule, on répartit les ${\displaystyle k^{n}}$ mots de longueur ${\displaystyle n}$ : chaque mot appartient à un et un seul collier. Si ce collier n'est pas apériodique, le mot n'est pas un mot primitif, et il est puissance d'un mot primitif unique dont la longueur ${\displaystyle d}$ divise ${\displaystyle n}$. Ce mot primitif appartient à un collier de longueur ${\displaystyle d}$. Ainsi, chaque mot de longueur ${\displaystyle k}$ est dans un collier apériodique de longueur divisant ${\displaystyle n}$, et chaque collier contient exactement d mots. Ceci prouve la formule.

Les colliers apériodiques apparaissent dans les contextes suivants :

• Le nombre de mots de Lyndon de longueur ${\displaystyle n}$ sur ${\displaystyle k}$ lettres : Tout collier apériodique correspond à un unique mot de Lyndon, de sorte que les mots de Lyndon forment un système de représentants de colliers apériodiques.
• ${\displaystyle M_{k}(n)}$ est la dimension de la composante homogène de degré ${\displaystyle n}$ de l'algèbre de Lie libre sur ${\displaystyle k}$ générateurs. C'est la formule de Witt[2]
• ${\displaystyle M_{k}(n)}$ est le nombre de polynômes unitaires irréductibles de degré ${\displaystyle n}$ sur un corps fini à ${\displaystyle k}$ éléments lorsque ${\displaystyle k}$ une puissance d'un nombre premier.
• C'est aussi l'exposant dans l'identité cyclotomique (en) :

${\displaystyle {1 \over 1-kz}=\prod _{j=1}^{\infty }\left({1 \over 1-z^{j}}\right)^{M_{k}(j)}}$

Voici les expressions des polynômes de colliers pour de petites valeurs de n :

• ${\displaystyle M_{k}(1)=k}$
• ${\displaystyle M_{k}(2)=(k^{2}-k)/2}$
• ${\displaystyle M_{k}(3)=(k^{3}-k)/3}$
• ${\displaystyle M_{k}(4)=(k^{4}-k^{2})/4}$
• ${\displaystyle M_{k}(5)=(k^{5}-k)/5}$
• ${\displaystyle M_{k}(6)=(k^{6}-k^{3}+k)/6}$
• Quand ${\displaystyle p}$ est un nombre premier, on a ${\displaystyle M_{k}(p^{n})=(k^{p^{n}}-k^{p^{n-1}})/p^{n}}$.

Enfin,

${\displaystyle \displaystyle M_{kr}(n)=\sum _{[i,j]=n}(i,j)M_{k}(i)M_{r}(j)}$,

où ${\displaystyle (i,j)}$ est le pgcd et ${\displaystyle [i,j]}$ est le ppcm de ${\displaystyle i}$ et ${\displaystyle j}$.

Le produit des nombres ${\displaystyle N_{k}(n)}$ de colliers de longueur ${\displaystyle n}$, sur ${\displaystyle k}$ symboles, admet une limite quand ${\displaystyle n}$ croît et ${\displaystyle k}$ est fixe ; c'est

${\displaystyle \lim _{n\to \infty }\prod _{m=1}^{n}N_{k}(m)X^{m}=\lim _{n\to \infty }{\frac {k^{n}}{n!}}1(1+X)(1+X+X^{2})\cdots (1+X+X^{2}+\cdots +X^{n-1}),}$.

Le coefficient de ${\displaystyle X^{k}}$ dans le développement du produit (au facteur ${\displaystyle k^{n}/n!}$ près) est le nombre de permutations de ${\displaystyle n}$ avec ${\displaystyle k}$ inversions, aussi appelé un nombre de MacMahon. C'est la suite A008302 de l'OEIS (Contribution de Mikhail Gaichenkov).

• Mot de Lyndon
• Problème du partage d'un collier
• Permutation
• Preuve par double dénombrement#Petit théorème de Fermat
• nombre de Forte (en) utilisé en musique atonale. Les nombres de Forte correspondent aux bracelets binaires de longueur 12.
• Necklace ring (en)

(en) Frank Ruskey, « Information on Necklaces, Lyndon Words, de Bruijn Sequences ».

• Portail des mathématiques