Ah le classique collier de perles, application de la formule de Burnside !
Tu peux jeter un coup d'oeil ici :
Le groupe qui agit ici c'est le groupe diédral à éléments, et il agit sur l'ensemble des coloriages (applications de l'ensemble des perles dans l'ensemble des couleurs). Le fait que soit premier (impair, disons) présente l'avantage qu'il y a peu de classes de conjugaisons dans le groupe : peux-tu en faire la liste ?

Je ne comprends rien...

As-tu vu en cours ou en TD la formule de Burnside pour compter le nombre d'orbites pour l'action d'un groupe sur un ensemble ?

ça me dit vaguement quelque chose, je cherche dans mon cours...

Bon, je viens de voir ton autre fil, je réalise que j'ai visé trop haut dans mes indications. Excuse-moi.

j'crois que je vais abandonner

La réponse pour qui veut s'y essayer :

Peux-tu mettre quelques éléments de ton raisonnement afin que je puisse essayer quand même de comprendre ne serait-ce que quelques notions ?

Je reviens à ma question : connais-tu la formule de Burnside ? Que dit-elle ?

Elle dit sous l'hypothèse que G et E sont finis :

Card = (1/Card G)xcard Fix g
où désigne l'ensemble des orbites.

@Cyril : Voici quelques exemples pratiques du lemme de Burnside (sic).

T. P.

Si tu as la formule de Burnside, l'énigme n'est plus qu'un exercice d'application.

Modélisation (celle qui est sous-entendue dans tous les exercices de type "collier de perles") : on fixe un polygone régulier à sommets. Pour chaque sommet, on choisit une couleur parmi les disponibles. Ceci fait un coloriage. Soit l'ensemble des coloriages.
Question : combien a-t-il d'éléments ?
Deux coloriages donnent le même collier si et seulement si on passe de l'un à l'autre par une isométrie du polygone. Le groupe des isométries du polygone régulier à sommets est le groupe diédral .
Question : que sais-tu de ? Quel est son ordre ? Peux-tu décrire ses éléments ?
Pour résumer, à la mode action de groupe : agit sur , et on veut compter les orbites.
Question : soit . Suivant le type de , dire combien il y a de coloriages fixes par (déterminer ).

Ceci fait il ne reste plus qu'à recoller les morceaux dans la formule de Burnside que tu as citée pour trouver le résultat que j'ai donné plus haut.

@Cyril : Ta question est récurrente. A titre d'exemple, voici un lien :

Errata :

@Cyril : Ta question est récurrente. A titre d'exemple, voici un lien : . Tu y remarqueras les interventions de Monsieur Michel Coste, auteur du papier que GaBuZoMeu t'a donné le 18-10-12 à 21:04. Cela me rappelle de vieux souvenirs.

T. P.

Pour X le nombre de coloriages, je dirais ceci :

On a p sommets. A chaque sommet on choisit parmi n couleurs DISPONIBLES.
Ainsi, pour le premier sommet, je prend
Puis, pour le second sommet, je prend
Et ainsi de suite, ainsi X =

Est-ce correct ?

Non. C'est vraiment un dénombrement élémentaire : le nombre d'applications de l'ensemble des p sommets dans l'ensemble des n couleurs.

X = { f: {ensemble des p sommets} {ensemble des n couleurs} ; f application } = n^p

Bon. Ca c'était l'entrée en matière. Maintenant, les autres questions : le groupe diédral, la recherche des coloriages fixes pour l'application de la formule de Burnside.

L'ordre du groupe diédral D_p est d'ordre 2p dont p réflexions et p rotations. On appelle groupe diédral tout gorupe non abélien engendré par deux éléments d'ordre deux, distintcts.

Je cherche à décrire un élément de ce groupe mais je ne trouve pas pour le moment.
Je dirais que les élements de ce groupe sont {0, ..., p-1}

En fait je dirai que D_p = < r, s > = {ri,ris, 0ip-1} ?

En l'occurrence ce qui est utile ici est de voir le groupe diédral comme groupe des isométries du polygone régulier (à côtés, ici premier impair).
Peux tu décrire les coloriages des sommets du polygone fixes par une telle isométrie ? Compter ces coloriages fixes suivant la classe de conjugaison de l'isométrie ?

Voilà ce que j'ai trouvé.

On appelle groupe diédral de dégré p et on note D_p, le stabilisateur de { e^(2ik)/n, pour k dans {0, ..., p-1} } via l'opération définie comme suit :
f.(x₁, ..., x_p) = (f(x₁, ..., f(x_n)) où f est une isométrie de allant dans ^p.
Le groupe diédral D_p est l'ensemble des isométries affines telles que l'image de D_p reste D_p.

Autrement dit, D_p agit sur les coloriages des p sommets.
D_p agit sur X.
Et là je suis encore paumé...

Prenons p=3 (un triangle équilatéral) et n=3 (Rouge, Vert, Bleu). Décris alors les isométries du triangle équilatéral. Pour chaque isométrie, décrit les coloriages fixes.

j'ai trouvé ceci regarde pour les isométries du triangle équilatéral :

On a 6 isométries pour le triangle équilatéral.

Pour la rotation, on a BVR=RBV=VRB
Est-ce exact ?

Je ne comprends pas ce que tu veux dire. Un coloriage fixe par une rotation, c'est un coloriage qui ne change pas quand on effectue la rotation. Si tu colories un sommet en rouge, un en vert et le dernier en bleu, le coloriage change quand on fait une rotation d'1/3 de tour, non ?

Les coloriages fixes sont : RRR, BBB, VVV seulement en fait ?

Ben oui...
Si on veut formaliser pour trouver les coloriage fixes pour une isométrie du groupe diédral : un coloriage est fixe par si et seulement si tous les sommets qui sont dans la même orbite pour l'action du groupe cyclique engendré par sont de la même couleur.
Si est une rotation d'1/3 de tour, les trois sommets du triangle équilatéral sont dans la même orbite.
Bon, et maintenant, peux-tu décrire les coloriages fixes par une symétrie du triangle équilatéral ?

Ce sont les coloriages où on a deux lettres identiques qui se suivent. Exemples : RBB, BBR, RBR

Je ne comprends pas ta réponse. Soient A,B,C les sommets du triangle équilatéral. Soit u la symétrie d'axe la médiatrice de BC. Quels sont les coloriages fixes par u, combien y en a-t-il ?
Par ailleurs, je te trouves très passif dans cette histoire. Alors, je te fixe un programme et je n'interviens plus tant que tu ne l'as pas rempli.
1°) Tu calcules tous les éléments qui figurent dans la formule de Burnside dans le cas de 3 perles (p=3) et 3 couleurs (n=3).
2°) Tu compares le résultat donné par Burnside avec le résultat que tu peux trouver par un dénombrement simple, pour vérifier.
3°) Une fois que tu as vérifié que ça colle, tu t'attaques au problème p premier impair et n quelconque.
Et hop !

Pour la symétrie u, en fait B va prendre la place de C et inversement. Donc si on a A de n'importe quelle couleur, par la symétrie rien ne change pour A.
Maintenant dès que la couleur de B est la même que celle de C, on aura un coloriage fixe. Donc on a :

A quelconque. B=C=Rouge, B=C=Vert, B=C=Bleu sont les coloriages fixes par u. Ainsi, on a 3x3=9 coloriages fixes ici.
Soit maintenant v la symétrie d'axe la médiatrice de AC, alors A=C=Rouge, A=C=Bleu, A=C=Vert sont fixes par u' (et ce quelquesoit la couleur de B). 9 coloriages fixes aussi.
De même pour la derniere médiatrice, 9 également.
Donc pour les symétries on a 27 coloriages fixes.

On fixe un triangle équilatéral à p=3 sommets donc. Pour chaque sommet, on choisit une couleur parmi les n=3  disponibles. Ceci fait un coloriage. Soit X l'ensemble des coloriages.
|X|=n^p=3³= 27 coloriages.
Deux coloriages donnent le même collier si et seulement si on passe de l'un à l'autre par une isométrie du triangle. Le groupe des isométries du triangle équilatéral est le groupe diédral D₃ qui a donc 6 éléments dont 3 symétries et 3 rotations.
Pour une rotation on a 3 coloriages fixes (BBB,RRR,VVV). Mais pour les 3 rotations, ce sont les mêmes.
Pour l'ensemble des rotations, on a donc que 3 coloriages fixes.
Pour les symétries, on a les coloriages fixes suivants : BRR, BVV, BBB (déjà compté), VRR, VBB, VVV (déjà compté), RVV, RBB, RRR (déjà compté). Donc 6 coloriages fixes de plus que pour les rotations.
Au total, 9 coloriages restent fixes par l'ensemble des isométries du triangles.

|Orb(X)|=1/|D₃| x |fix(D₃)|
        =1/6 x 9
C'est bizarre....

Bel effort. Mais tu perds complètement les pédales dans l'application de la formule de Burnside. Relis-la soigneusement pour comprendre ce qu'elle dit exactement.
Par ailleurs, tu comptes trois rotations. Trois rotations d'1/3 de tour dans un sens ou dans l'autre ? Es-tu sûr ?

En fait, je ne repère pas les éléments dans la formule là, je suis un peu perdu. Peux-tu me dire la formule appliquée au sujet ?
Pour les rotations, il faut toutes les compter ? Pourtant les coloriages fixes sont les mêmes, on va donc les compter plusieurs fois dans burnside ?

Ecris la formule de Burnside en précisant bien tout (en particulier l'ensemble d'indices pour la somme).

|X/G| = 1/|G| _gG |Fix(g)|

Et alors ?

Ici X est l'ensemble des coloriages, mais que vaut X/G ?
Ensuite, G correspond à D₃.
Enfin Fix(g) sont les coloriages fixes pour g qui ici est donc un triangle ?
Désolé mais franchement c'est difficile pour moi..

J'ai l'impression que tu régresses...
Bon alors je choisis la solution de facilité : je balance une solution en reprenant des bouts de mes messages précédents, et tu te débrouilles avec.

On suppose premier impair.

Modélisation (celle qui est sous-entendue dans tous les exercices de type "collier de perles") : on fixe un polygone régulier à sommets. Pour chaque sommet, on choisit une couleur parmi les disponibles. Ceci fait un coloriage. Soit l'ensemble des coloriages. Le cardinal de est égal à , le cardinal de l'ensemble des applications d'un ensemble à éléments dans un ensemble à éléments.

Deux coloriages donnent le même collier si et seulement si on passe de l'un à l'autre par une isométrie du polygone. Le groupe des isométries du polygone régulier à sommets est le groupe diédral . Les éléments de sont
1°) l'identité.
2°) Les rotations d'angle pour . Puisque est premier, chacune de ces rotations est d'ordre . Il y a telles rotations.
3°) Les symétries orthogonales dont les axes sont les droites joignant un sommet au milieu du côté opposé (puisque est impair). Il y a telles symétries.
Ceci clôt la liste des éléments du groupe .

Pour résumer, à la mode action de groupe : agit sur , et on veut compter les orbites. Le nombre d'orbites pour l'action de sur est donné par la formule de Burnside : , où est l'ensemble des coloriages laissés fixes par l'élément de .
1°) L'identité laisse fixe n'importe quel coloriage : donc  .
2°) Le sous-groupe cyclique engendré par une rotation d'ordre agit transitivement sur l'ensemble des sommets. Ceci montre que les seuls coloriages laissés fixes par une telle rotation sont les coloriages en une seule couleur. On a donc, si est une rotation différente de l'identité dans , . Rappelons qu'il y a telles rotations.
3°) Une symétrie dans ne bouge pas le sommet situé sur son axe, et échange chaque autre sommet avec son symétrique. Un coloriage est fixe par la symétrie si et seulement si chaque sommet non situé sur l'axe est de la même couleur que son symétrique. Un sommet sur l'axe, paires de sommets symétriques, cela fait que si est une symétrie. Il y a symétries.

Récapitulons : la formule de Burnside nous dit que le nombre de colliers différents est

Oulala merci énormément pour le temps que tu as pris pour m'aider ! Je pense avoir vraiment compris globalement, je vais m'attarder aux détails et je te remercie beaucoup !

Juste une petite question, tu as écris :
"Dp agit sur X ... l'action de X sur Dp" C'est plutot l'action de Dp sur X non ?

Oui, c'est une coquille : il s'agit bien de l'action de sur .

Je te remercie Gabu!