Le mot anglais derangement se traduit par: dérangement, voir:
http://www.guetali.fr/home/cgrnay/journal.htm
mais pour le collier, mystère!
Alain Larroche.

Envoyer votre réponse.

Réponse de Pierre Renfer du 27/05/01 à 22h 47 :

                                 ROULETTES ET COLLIERS

 1) Une roulette circulaire est partagée en n secteurs égaux et chaque secteur possède l’une des couleurs d’une palette de c couleurs.

Dénombrer les colliers, étant entendu qu’on identifie les colliers qui se correspondent par une rotation ou par un retournement ( symétie axiale).

Des rappels sur les actions de groupe

Définition

Une opération (à gauche) d’un groupe G sur un ensemble E est une application

vérifiant les deux propriétés :

, e désignant l’élément neutre de G

Orbites

L’opération définit sur E une relation d’équivalence par :

Les classes d’équivalence sont appelées les orbites.

Le choix du mot orbite est un clin d’oeil à un exemple facile d’opération de groupe, où E est le plan affine euclidien et G le groupe des rotations autour d’un centre O donné, avec .

Les orbites sont alors les cercles concentriques, de centre O.

 Stabilisateur d’un élément

Pour tout x dans E, on considère ;

S(x) est un sous-groupe de G, appelé stabilisateur de x.

 Une première formule de dénombrement

Si G est un groupe fini et si désigne l’orbite de x, alors :

Démonstration

Pour un élément y de , soit

Si est un élément particulier de , on peut définir la bijection :

Donc

Et :

 5) Théorème de Burnside-Frobenius

Soit l'ensemble des orbites.

Pout tout élément de G, on pose :

Alors :

Démonstration

Soit

Si l’on interdit aux roulettes de tourner, le problème est facile : il y a coloriages possibles.

Soit E l’ensemble de ces coloriages.

On fait opérer sur E le groupe cyclique G engendré par une rotation d’ordre n.

Alors la réponse au problème est le nombre d’orbites, qui sera fourni par le théorème de Burnside-Frobenius.

Il reste à calculer pour toute rotation du groupe G.

L’ordre d’un élément du groupe G est un diviseur d de n.

Le groupe cyclique engendré par opère sur l’ensemble des n secteurs et définit n/d orbites.

Pour qu’un coloriage de E appartienne à , il faut et il suffit que les secteurs d’une même orbite soient d’une même couleur.

Il s’agit donc de choisir une couleur pour chaque orbite et :

Le nombre de rotation d’ordre d est , où désigne l’indicateur d’Euler.

La formule de Burnside-Frobenius donne finalement :

Application au problème des colliers

 

Là encore, le problème est facile si l’on interdit les rotations et retournement du collier :

Il y a alors coloriages posibles.

On fait opérer sur l’ensemble E de ces coloriages le groupe diédral des isométries conservant un polygone régulier à n sommets, qui contient les n rotations comme pour les roulettes et n symétries axiales.

Pour les symétries, on est amené à discuter suivant la parité de n.

Cas où n est impair

C’est le cas le plus facile : pour toute symétrie , l’axe passe par une perle et les (n-1) autres perles se répartissent en (n-1)/2 paires contenant deux perles symétriques.

Pour un élément de , il s’agit de choisir la couleur de la perle de l’axe et les couleurs des (n-1)/2 paires ; donc :

La formule de Burnside-Frobenius donne finalement :

Cas où n est pair

Il existe alors deux types de symétries : celles dont l’axe ne passe par aucune perle et celles dont l’axe passe par deux perles.

Si est une symétrie du premier type, il s’agit, pour un élément de , de choisir la couleur des n/2 paires de deux perles symétriques ; donc :

Si est une symétrie du second type, il s’agit, pour un élément de , de choisir la couleur des deux perles de l’axe et des (n-2)/2 paires de deux perles symétriques ; donc :

Le groupe diédral contient n/2 symétries de chaque type.

La formule de Burnside-Frobenius donne finalement :