Qu'est-ce qu'une permutation de collier ?
Une permutation de collier (aussi appelée arrangement en bracelet, ou « permutation juzu » en japonais) compte le nombre de façons distinctes de disposer n objets différents le long d'une boucle fermée, sachant que deux dispositions sont considérées comme identiques si l'on peut passer de l'une à l'autre par une rotation de la boucle ou en la retournant (une symétrie). Elle va un cran plus loin que la permutation circulaire : cette dernière n'élimine que la symétrie de rotation, tandis que le collier supprime également la symétrie miroir.
Comment utiliser ce calculateur
Saisissez le nombre d'objets distincts n (un entier positif ou nul) et le calculateur renvoie le nombre d'arrangements de collier distincts. À titre de comparaison, il affiche aussi le nombre de permutations linéaires (\(n!\)) et le nombre de permutations circulaires (\((n-1)!\)). Comme les factorielles croissent extrêmement vite, le résultat est calculé en arithmétique entière exacte à précision arbitraire : même les grandes valeurs de n s'affichent ainsi sans aucune approximation.
La formule expliquée
Pour n arrangements linéaires, il existe \(n!\) ordonnancements. En fixant un objet sur la boucle afin d'éliminer les n rotations équivalentes, il reste \((n-1)!\) arrangements circulaires. Un collier considère en plus qu'un motif horaire et son image miroir antihoraire sont identiques : on divise donc encore une fois par 2 :
$$P = \frac{(n - 1)!}{2}$$ pour \(n \ge 3\).
Pour n = 0, 1 et 2, la formule simple donnerait un résultat non entier ou un sous-comptage ; par convention, la réponse est donc 1 dans chacun de ces cas : il existe exactement une boucle distincte (ou une boucle vide).
Exemple détaillé
Pour n = 5 : $$\frac{(5 - 1)!}{2} = \frac{4!}{2} = \frac{24}{2} = 12$$ colliers distincts. Pour n = 6 : \(\frac{5!}{2} = \frac{120}{2} = 60\). Pour n = 4 : \(\frac{3!}{2} = 3\).
FAQ
En quoi est-ce différent d'une permutation circulaire ? Une permutation circulaire vaut \((n-1)!\) : elle compte les rotations comme identiques mais considère les images miroir comme distinctes. Une permutation de collier divise ce résultat par 2, car les retournements sont eux aussi traités comme identiques.
Pourquoi la réponse est-elle 1 pour n = 2 ? Avec deux objets, il n'existe qu'une seule boucle possible ; la tourner ou la retourner ne fait qu'échanger les deux positions, si bien que toutes les dispositions coïncident. La formule \(\frac{(2-1)!}{2} = \frac{1}{2}\) n'a pas de sens ici, d'où le recours à un cas particulier.
La formule suppose-t-elle que tous les objets sont différents ? Oui. Ce calculateur part du principe que les n objets sont distincts. Si certains objets sont identiques, le décompte est plus faible et nécessite un traitement différent (théorie de Burnside/Pólya).
