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}\varphi (d)k^{n/d}$

colliers de longueur $n$ sur un alphabet de taille $k$. Ici, $\varphi$ est l'indicatrice d'Euler.

Pour $k=2$, $(N_{2}(n))_{n}$ est référencée suite A000031 de l'OEIS et la suite double $(N_{k}(n))_{n,k}$ référencée suite A054631 de l'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}\varphi (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. ${\displaystyle S(n,k)}$ représente les Nombres de Stirling de seconde espèce. ${\displaystyle L_{k}(n)}$ est la suite A087854 de l'OEIS et est reliée à ${\displaystyle N_{k}(n)}$ au travers des coefficients binomiaux:

${\displaystyle N_{k}(n)=\sum _{j=1}^{k}{\binom {k}{j}}L_{k}(n)}$

et

${\displaystyle L_{k}(n)=\sum _{j=1}^{k}(-1)^{k-j}{\binom {k}{j}}N_{k}(n)}$

Nombre de bracelets

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

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)={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
• $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-kz}=\prod _{j=1}^{\infty }\left({1 \over 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,

$\displaystyle 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

$\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

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

Notes et références

Notes

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

Références

• M. Lothaire, Combinatorics on words, Cambridge University Press, coll. « Cambridge Mathematical Library », 1997, xviii+238 (ISBN 978-0-521-59924-5, DOI 10.1017/CBO9780511566097, MR 1475463, présentation en ligne)
  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)
• (en) Richard P. Stanley, Enumerative Combinatorics [détail des éditions] (présentation en ligne)
• C. Moreau, « Sur les permutations circulaires distinctes », Nouvelles annales de mathématiques, journal des candidats aux écoles polytechnique et normale, 2^e série, vol. 11,‎ 1872, p. 309–314 (lire en ligne)
• Nicholas Metropolis et Gian-Carlo Rota, « Witt vectors and the algebra of necklaces », Advances in Mathematics, vol. 50, n^o 2,‎ 1983, p. 95–125 (DOI 10.1016/0001-8708(83)90035-X, MR 723197, zbMATH 0545.05009)
• Gabriele Fici, Antonio Restivo et Laura Rizzo, « Minimal forbidden factors of circular words », Theoretical Computer Science, vol. 792,‎ 2019, p. 144–153 (DOI 10.1016/j.tcs.2018.05.037)

Lien externe

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