Collier (combinatoire)

En combinatoire, un collier de k perles de longueur n est un mot circulaire ou encore une classe d'équivalence de suites de n symboles sur un alphabet de taille k, en considérant comme équivalents tous les décalages circulaires de la suite. Un collier peut être vu comme étant formé de n perles de k couleurs enfilés en cercle.

Un bracelet, aussi appelé collier libre ou collier reversible est une classe d'équivalence de suites de symboles sous les deux opération de décalage circulaire et de réflexion ou retournement.

Dans l'exemple ci-contre, le bracelet est la classe d'équivalence du mot ABCBAAC ; selon que l'on lit dans sens direct ou le sens inverse, il y a deux colliers, qui sont les classes des mots ABCBAAC et CAABCBA.

En termes techniques, un collier est une orbite de l'action du groupe cyclique d'ordre n, alors qu'un bracelet est une orbite de l'action du groupe diédral.

Un bracelet, deux colliers.

Dénombrements de colliers

Nombre de colliers

Il y a

$N_k(n)=\frac{1}{n}\sum _{d\mid n}\phi (d)k^{n/d}$

colliers de longueur $n$ sur un alphabet de taille $k$. Ici, $\phi$ est l'indicatrice d'EulerModèle:,.

Pour $k=2$, $(N_2(n){)}_n$ est référencée Modèle:OEIS et la suite double $(N_k(n){)}_{n,k}$ référencée Modèle:OEIS.

Pour $n=3$ et $n=4$ les colliers sont 000,001,011,111 et 0000,0001,0011,0101,0111,1111.

Il y a aussi

$L_k(n)=\frac{k!}{n}\sum _{d\mid n}\phi (d)S(\frac{n}{d},k)$

colliers de longueur $n$ sur un alphabet de taille $k$ ou chaque lettre est présente au moins une fois. $S(n,k)$ représente les Nombres de Stirling de seconde espèce. $L_k(n)$ est la Modèle:OEIS et est reliée à $N_k(n)$ au travers des coefficients binomiaux:

$N_k(n)=\sum _{j=1}^k(\genfrac{}{}{0ex}{}{k}{j})L_k(n)$

et

$L_k(n)=\sum _{j=1}^k(-1{)}^{k-j}(\genfrac{}{}{0ex}{}{k}{j})N_k(n)$

Nombre de bracelets

Il y a

$B_k(n)=\{\begin{array}{cc}\frac{1}{2}{N}_k(n)+\frac{1}{4}(k+1)k^{n/2}& \text{si }n\text{ est pair,}\\ \\ \frac{1}{2}{N}_k(n)+\frac{1}{2}{k}^{(n+1)/2}& \text{si }n\text{ est impair.}\end{array}$

bracelets de longueur $n$ sur un alphabet de taille $k$, où $N_k(n)$ est le nombre de colliers de longueur $n$ sur un alphabet de taille $k$.

Exemples

Exemples de colliers

Si les $n$ perles d'un collier de longueur $n$ sont toutes distinctes, alors le nombre de colliers est $n!/n=(n-1)!$, le nombre de permutations circulaires d'ordre $n$.

Si, au contraire, toutes les perles sont identiques, il n'y a qu'un seul collier de cette couleur, donc au total autant de collier que de symboles dans l'alphabet.

Exemples de bracelets

Si les $n$ perles d'un collier de longueur $n$ sont toutes distinctes, le nombre de bracelets est $n!/(2n)$ pour $n>1$. Ce n'est pas $B_n(n)$, puisque dans ce nombre on compte aussi des bracelets dont les perles ne sont pas toutes distincts.

Colliers apériodiques

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

$M_k(n)=\frac{1}{n}\sum _{d\mid n}\mu (d)k^{n/d}$.

Ici, $\mu$ est la fonction de Möbius. Les fonctions $M_k(n)$ sont aussi appelés les polynômes de colliers (en la variable $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 $k=2$, la suite des $M_k(n)$ est la Modèle:OEIS. Pour $n=3$ et $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

$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 $k^n$ mots de longueur $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 $d$ divise $n$. Ce mot primitif appartient à un collier de longueur $d$. Ainsi, chaque mot de longueur $k$ est dans un collier apériodique de longueur divisant $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 $n$ sur $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.
• $M_k(n)$ est la dimension de la composante homogène de degré $n$ de l'algèbre de Lie libre sur $k$ générateurs. C'est la formule de Witt
• $M_k(n)$ est le nombre de polynômes unitaires irréductibles de degré $n$ sur un corps fini à $k$ éléments lorsque $k$ une puissance d'un nombre premier.
• C'est aussi l'exposant dans l'Modèle:Lien :

$\frac{1}{1-kz}=\prod _{j=1}^{\mathrm{\infty }}{\left(\frac{1}{1-z^j}\right)}^{M_k(j)}$

Premières valeurs

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

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

Enfin,

$M_{kr}(n)=\sum _{[i,j]=n}(i,j)M_k(i)M_r(j)$,

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

Formule du produit de colliers

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

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

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

Articles connexes

• Mot de Lyndon
• Problème du partage d'un collier
• Permutation
• Preuve du petit théorème de Fermat par double dénombrement
• Modèle:Lien utilisé en musique atonale. Les nombres de Forte correspondent aux bracelets binaires de longueur 12.
• Modèle:Lien
• Permutation circulaire lexicographiquement minimale

Notes et références

Références

• Modèle:OuvrageModèle:Commentaire biblio
• Modèle:Enumerative Combinatorics
• Modèle:Article
• Modèle:Article
• Modèle:Article

Lien externe

Modèle:En Frank Ruskey, « Information on Necklaces, Lyndon Words, de Bruijn Sequences ».