Collier (combinatoire)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En combinatoire, a collier de k perles de longueur n est 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[modifier | modifier le code]

Nombre de colliers[modifier | modifier le code]

Il y a

N_k(n)=\frac1n\sum_{d\mid n}\varphi(d)k^{n/d}

colliers de longueur n sur un alphabet de taille k. Ici, \varphi est l'indicatrice d'Euler[1]. Pour k=2, c'est la suite A000031 de l'OEIS. Pour n=3 et n=4 les colliers sont 000,001,011,111 et 0000,0001,0011,0101,0111,1111.

Nombre de bracelets[modifier | modifier le code]

Il y a


B_k(n) = 
\begin{cases}
{1\over 2}N_k(n) + {1\over 4}(k+1)k^{n/2} & \text{si }n\text{ est pair,} \\  \\
{1\over 2}N_k(n) + {1 \over 2}k^{(n+1)/2} & \text{si }n\text{ est impair.}
\end{cases}

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[modifier | modifier le code]

Exemples de colliers[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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)={1\over 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 suite A001037 de l'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[2]
  • 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'identité cyclotomique (en) :
{1 \over 1-k z}=\prod_{j=1}^\infty\left({1 \over 1-z^j}\right)^{M_k(j)}

Premières valeurs[modifier | modifier le code]

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,

\displaystyle M_{kr}(n)=\sum_{[i,j]=n}(i,j)M_k(i)M_r(j),

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

Formule du produit de colliers[modifier | modifier le code]

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

\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 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 suite A008302 de l'OEIS (Contribution de Mikhail Gaichenkov).

Articles connexes[modifier | modifier le code]

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

(en)/(en) Cet article est partiellement ou en totalité issu des articles intitulés en anglais « Necklace (combinatorics) » (voir la liste des auteurs) et en anglais « Necklace polynomial » (voir la liste des auteurs)

Références[modifier | modifier le code]

Lien externe[modifier | modifier le code]

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