Voir la source de Collier (combinatoire)

En [[combinatoire]], un '''collier''' de ''k'' perles de longueur ''n'' est un [[Mot (mathématiques)#Terminologie supplémentaire| mot circulaire]] ou encore une  [[Relation d'équivalence#Classe d'équivalence|classe d'équivalence]] de suites de  ''n'' symboles sur un [[alphabet]] de taille  ''k'', en considérant comme équivalents tous les  [[décalage circulaire|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 [[Action de groupe (mathématiques)|orbite]] de l'action du [[groupe cyclique]] d'ordre ''n'', alors qu'un bracelet est une orbite de l'action du [[groupe diédral]].
[[Fichier:Proofs-of-Fermats-Little-Theorem-bracelet1.svg|thumb|Un bracelet, deux colliers.]]
== Dénombrements de colliers ==

=== Nombre de  colliers ===
Il y a 

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

colliers de longueur <math>n</math> sur un alphabet de taille <math>k</math>. Ici, <math>\varphi</math> est l'[[indicatrice d'Euler]]<ref>{{MathWorld|nom_url=Necklace|titre=Necklace}}</ref>{{,}}<ref>{{Lien web |titre=Dénombrement des colliers à n perles et c couleurs |url=http://agregmaths.free.fr/doc/docs_nicolas/developpement%20Algebre/Denombrement%20colliers%20de%20perles%202.pdf |site=agregmaths.free.fr/}}</ref>. 

Pour <math>k=2</math>, <math>(N_2(n))_n</math> est référencée {{OEIS|id=A000031}} et la suite double <math>(N_k(n))_{n,k}</math>  référencée {{OEIS|id=A054631}}. 

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

Il y a aussi

:<math>L_k(n)=\frac{k!}{n}\sum_{d\mid n}\varphi(d)S(\frac{n}{d}, k)</math> 

colliers de longueur <math>n</math> sur un alphabet de taille <math>k</math> ou chaque lettre est présente au moins une fois. <math>{\displaystyle S(n,k)}</math> représente les [[Nombre de Stirling de seconde espèce|Nombres de Stirling de seconde espèce]]. <math>{\displaystyle L_{k}(n)}</math> est la {{OEIS|id=A087854}} et est reliée à <math>{\displaystyle N_{k}(n)}</math> au travers des [[Coefficient binomial|coefficients binomiaux]]:

:<math>{\displaystyle N_{k}(n)=\sum _{j=1}^{k}{\binom {k}{j}}L_{k}(n)}</math>

et

:<math>{\displaystyle L_{k}(n)=\sum _{j=1}^{k}(-1)^{k-j}{\binom {k}{j}}N_{k}(n)}</math>

=== Nombre de  bracelets ===
Il y a 
:<math>
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}
</math>
bracelets de longueur <math>n</math> sur un alphabet de taille <math>k</math>, où <math>N_k(n)</math>
est le nombre de colliers de longueur <math>n</math> sur un alphabet de taille <math>k</math>. 

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

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 <math>n</math> perles d'un collier de longueur <math>n</math> sont toutes distinctes, le nombre de bracelets est <math>n!/(2n)</math> pour <math>n>1</math>. Ce n'est pas <math>B_n(n)</math>, puisque dans ce nombre on compte aussi des bracelets dont les perles ne sont pas toutes distincts.

== Colliers apériodiques ==
[[File:Bracelets33.svg|thumb|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 (mathématiques) |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
:<math>M_k(n)={1\over n}\sum_{d\mid n}\mu(d)k^{n/d}</math>.
Ici, <math>\mu</math> est la [[fonction de Möbius]]. Les fonctions <math>M_k(n)</math> sont aussi appelés les '''polynômes de colliers''' (en la variable <math>k</math>), et la formule ci-dessus est attribuée au [[Charles Paul Narcisse Moreau|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 <math>k=2</math>, la suite des <math>M_k(n)</math> est la {{OEIS|id=A001037}}. Pour <math>n=3</math> et <math>n=4</math>, les colliers apériodiques binaires sont 001,011 et 0001,0011,0111.

La formule ci-dessus est dérivée de l'expression 
:<math>k^n = \sum_{d\,|\,n} d \, M_k(d)</math>
et s'obtient par [[inversion de Möbius]]. 

Pour établir la formule, on répartit les 
<math>k^n</math> mots de longueur <math>n</math> : chaque mot appartient à un et un seul collier. Si ce collier n'est pas apériodique, le mot n'est pas un [[mot (mathématiques)|mot primitif]], et il est puissance d'un mot primitif unique dont la longueur <math>d</math> divise <math>n</math>. Ce mot primitif appartient à un collier de longueur <math>d</math>. Ainsi, chaque mot de longueur <math>k</math> est dans un collier apériodique de longueur divisant <math>n</math>, et chaque collier contient exactement d mots. Ceci prouve la formule.
 
Les colliers apériodiques apparaissent dans les contextes suivants :

*Le nombre de  [[mot de Lyndon|mots de Lyndon]] de longueur <math>n</math> sur <math>k</math> 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.
* <math>M_k(n)</math> est la dimension de la composante homogène de degré <math>n</math> de l'[[algèbre de Lie]] libre sur <math>k</math> générateurs. C'est la ''formule de Witt''<ref>{{harvsp|Lothaire|1997|p=79,84}}</ref>
* <math>M_k(n)</math> est le nombre de polynômes unitaires irréductibles de degré <math>n</math> sur un [[corps fini]] à <math>k</math> éléments lorsque <math>k</math> une puissance d'un [[nombre premier]].
* C'est aussi l'exposant dans l'{{Lien|fr=identité cyclotomique|lang=en|trad=cyclotomic identity}} :
:<math>{1 \over 1-k z}=\prod_{j=1}^\infty\left({1 \over 1-z^j}\right)^{M_k(j)}</math>

== Premières valeurs ==
Voici les expressions des polynômes de colliers pour de petites valeurs de ''n'' :
*<math>M_k(1)=k</math>
*<math>M_k(2)=(k^2-k)/2</math>
*<math>M_k(3)=(k^3-k)/3</math>
*<math>M_k(4)=(k^4-k^2)/4</math>
*<math>M_k(5)=(k^5-k)/5</math>
*<math>M_k(6)=(k^6-k^3+k)/6</math>
*Quand <math>p</math> est un nombre premier, on a  <math>M_k(p^n)=(k^{p^n}-k^{p^{n-1}})/p ^n</math>.
Enfin, 
:<math>\displaystyle M_{kr}(n)=\sum_{[i,j]=n}(i,j)M_k(i)M_r(j)</math>,
où <math>(i,j)</math> est le [[pgcd]] et <math>[i,j]</math> est le [[Plus petit commun multiple|ppcm]] de <math>i</math> et <math>j</math>.

== Formule du produit de colliers ==
Le produit des nombres <math>N_k(n)</math> de colliers de longueur <math>n</math>, sur <math>k</math> symboles, admet une limite quand <math>n</math> croît et <math>k</math> est fixe ; c'est

:<math>\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}),</math>.
Le coefficient de  <math>X^k</math> dans le développement du produit (au facteur <math>k^n/n!</math> près) est le nombre de [[Permutation|permutations]] de <math>n</math> avec  <math>k</math> [[permutation|inversions]], aussi appelé un nombre de [[Percy Alexander MacMahon |MacMahon]]. C'est la {{OEIS|id=A008302}} (Contribution de Mikhail Gaichenkov).

== Articles connexes ==

* [[Mot de Lyndon]]
* [[Problème du partage d'un collier]]
* [[Permutation]]
* [[Preuve par double dénombrement#Petit théorème de Fermat|Preuve du petit théorème de Fermat par double dénombrement]]
* {{Lien|trad=Forte number|fr=nombre de Forte}} utilisé en [[musique atonale]]. Les nombres de Forte correspondent aux bracelets binaires de longueur 12.
* {{Lien|Necklace ring}}
* [[Permutation circulaire lexicographiquement minimale]]

== Notes et références ==
=== Notes ===
{{Références}}
{{Traduction/Référence|lang1=en|art1=Necklace (combinatorics)|id1=530741736
 |lang2=en|art2=Necklace polynomial|id2=516505844 |type=note}}
=== Références ===
*{{Ouvrage | auteur1=[[M. Lothaire]]
| titre=Combinatorics on words 
| présentation en ligne= http://ebooks.cambridge.org/ebook.jsf?bid=CBO9780511566097
| éditeur=[[Cambridge University Press]]
| collection=Cambridge Mathematical Library
| doi = 10.1017/CBO9780511566097
| math reviews = 1475463
| isbn=978-0-521-59924-5
| année=1997
| pages totales=xviii+238}}{{Commentaire biblio
|Seconde édition, légèrement révisée, du livre paru sous le même nom, en 1983, chez Addison-Wesley, dans la série « Encyclopedia of Mathematics and its Application », {{ISBN|978-0-201-13516-9}}}}
*{{Enumerative Combinatorics}}
*{{Article|prénom1=C.|nom1=Moreau
 |titre=Sur les permutations circulaires distinctes
 |année=1872
 |journal=[[Nouvelles annales de mathématiques]], journal des candidats aux écoles polytechnique et normale
 |série=2| volume=11 
 | pages=309–314
 |url=http://www.numdam.org/item?id=NAM_1872_2_11__309_0 }}
*{{article 
| auteur1=[[Nicholas Metropolis]] 
| auteur2=[[Gian-Carlo Rota]] 
| titre=Witt vectors and the algebra of necklaces 
| doi=10.1016/0001-8708(83)90035-X | math reviews=723197 | zbl=0545.05009 | année=1983 
| journal=[[Advances in Mathematics]] 
| volume=50 | numéro=2 | pages=95–125}}
* {{article
 |nom1=Fici|prénom1=Gabriele
 |nom2=Restivo|prénom2=Antonio |lien auteur2= Antonio Restivo
 |nom3=Rizzo|prénom3=Laura
 |titre=Minimal forbidden factors of circular words
 |journal=Theoretical Computer Science
 |volume=792|année=2019
 |pages=144–153
 |doi=10.1016/j.tcs.2018.05.037}}

== Lien externe ==
{{en}} Frank Ruskey, [http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html  « Information on Necklaces, Lyndon Words, de Bruijn Sequences »].

{{Portail|mathématiques}}

[[Catégorie:Combinatoire]]
[[Catégorie:Combinatoire des mots]]