Coloriages et roulette

Riemann_lapins_cretins

Bonjour.

Il y a un problème assez connu consistant à dénombrer le nombre de coloriages possibles avec q couleurs d'une roulette à N secteurs, avec la règle que deux coloriages déduits l'un de l'autre en tournant la roulette sont considérés identiques.

J'avais trouvé la solution en cogitant plusieurs jours et j'imagine que la plupart des gens la connaissent ici (ce qui n'est pas une raison pour la poster, laissons les cliqueurs curieux se creuser la tête s'ils ne connaissent pas).

Je me demandais juste s'il y avait une classe de problèmes semblables, histoire de m'entraîner à maîtriser plus en profondeur certains groupes. Il me semble que Polya avait développé pas mal d'énigmes similaires.

Merci !

Thibaut

Bonsoir "Lapins-Crétins" (c'est pas joyeux cet avatar),

Je suis intéressé par ton problème de dénombrement mais je ne comprends pas le problème.
Pour moi, il s'agit d'un problème d'analyse combinatoire.
Mais encore faut-il définir des règles comme q < N, moins de couleurs que de secteurs, non ?

Est-ce que tu pourrais reformuler le problème plus précisément ?
Merci, et je serai ravi de décortiquer le cortex pour ce problème

Sinon, pour 7€, tu as un ré-édition du problème d'entrée à Stanford des années 70-80.
Tu trouveras plein de problèmes appliqués très intéressants allant de la combinatoire sur le jeu de tennis à la géométrie en petite dimension.
The Stanford Mathematics Problem Book: With Hints and Solutions].

Pour ton problème, quelles sont les hypothèses et conditions du dénombrement ? Qu'est-ce qu'un coloriage dans le formalisme mathématique ? Une suite de couleurs ? Ou autre ?

purple

Dans ma tête le problème est bien posé Thibaut, de manière plus pédante on pourrait l'énoncer ainsi :
Soit $R = \{1, \ldots, N\}$.
Soit $\sim$ la relation d'équivalence entre deux partitions de $R$ "être égales à décalage circulaire près".
Calculer $Card(R/\sim)$.
Me trompé-je RLC ?

Thibaut

Bonsoir Purple,

En vérité, j'ai toujours eu des problèmes depuis le lycée à comprendre les énoncés relevant de la combinatoire, ce qui m'a posé des problèmes quand je devais étudier les probabilités discrètes (alors que j'ai moins de problème à comprendre le calcul stochastique e.g. appliqué à la finance).

Oui, du coup, avec la concision de ta formulation, je comprends mieux.
Du coup, je vais essayer de terminer la soirée avec un peu de r***m et ce problème à résoudre.

Merci, Purple,
PS: rien n'est plus pédant qu'être loquace dans l'intention de ne pas être laconique

Riemann_lapins_cretins

Thibaut : de base je voulais mettre Riemann Origins mais je pensais que personne ne comprendrait le jeu de mots sur ce forum, étant donné la tranche d'âge. J'ai choisi quelque chose de plus explicite qui parle plus à la culture populaire qu'aux adeptes de jeux vidéos.
Quant à l'avatar, il a une histoire sur ce forum !

Purple : exactement !

Indice : c'est bien un problème d'algèbre, je ne me suis pas trompé de forum.

Thibaut

Bonsoir,

Il est tard mais j'ai besoin d'indices pour le problème qui est bien un problème de combinatoire mais impliquant la notion de groupe fini.

Dîtes-moi juste ce que je dois utiliser pour trouver le cardinal du quotient.
1/ Actions de groupe et Formule de Burnside ?
2/ Le Théorème de Lagrange (l'ordre d'un sous-groupe fini divise le le cardinal du groupe qui l'a engendré ?)
3/ Le lemme/principe des bergers ?

Merci, je vais mourir idiot, ce soir

Id Est

Bonsoir,

Sans faire à votre place, le 1) me semble tout indiqué.

Cordialement.

Thibaut

Bonsoir Riemann-Origins,

Oui, je confirme, c'est un problème d'Algèbre, l'Algèbre qui permet efficacement de résoudre le problème mais à l'origine, il s'agit bien de combinatoire (j'ai vérifié: c'est un problème qui a été décortiqué par des Algébristes).

Du coup, est-ce que tu peux me confirmer une ou deux pistes que j'ai postées avant ?
1/ Théorème de Burnside ? (Formule des classes d'équivalences et cardinaux de sous-groupes engendrés)
2/ Théorème de Lagrange ? (relation arithmétique entre un sous-groupe fini d'un groupe fini)
3/ Lemme/Principe des Bergers ? (dénombrer des moutons en fonction du nombre de pattes) (relation d'équivalence: chaque mouton a exactement 4 pattes, donc: pour 8 pattes, il y a deux moutons)

Ce que je sais (si erreur)

C'est que le Card(R/~) du quotient est fini et et est un diviseur du groupe R. (Théorème de Lagrange).

Lemme des bergers — Si un ensemble E possède une partition en p sous-ensembles contenant chacun r éléments, alors E contient p × r éléments.

Formule des classes, formule de Burnside
À travers les notions d'orbite et de stabilisateur, les actions de groupe sont un outil commode en combinatoire. D'autre part, un certain nombre de propriétés concernant la structure de certains groupes peuvent être démontrées par des arguments de dénombrement.

Merci

Thibaut

Id Est écrivait : http://www.les-mathematiques.net/phorum/read.php?3,2254122,2254188#msg-2254188
[Inutile de recopier l'avant-dernier message. Un lien suffit. AD]

---

Bonsoir Id Est,

Merci pour l'indication, je farfouillais dans tous les sens une piste et effectivement, Burnside me paraissait plus efficace.
Je vais voir ça demain, il est tard, et il a fait soif.
Merci.

Riemann_lapins_cretins

Effectivement Burnside appliqué directement à un groupe et une action qui semblent évidents.
Calculer les stabilisateurs est l'étape la plus dure mais pas bien délicate non plus. La somme obtenue dans la formule reste implicite et n'a à ma connaissance pas de forme simple.

Par conséquent ma question revient à avoir des exercices pour me faire calculer des stabilisateurs plus compliqués, ce qui me semble un bon moyen de faire connaissance avec certains groupe. Le diédral par exemple, plutôt facile dans les bases mais assez bête noire pour les propriétés pointues. Il suffirait d'ajouter une condition d'égalité de deux coloriages obtenus par symétrie à mon avis, me trompe-je ?

Thibaut

Bonsoir Riemann-LC,

Oulah, si tu touches au diédral, va te falloir plonger en Théorie Géométrique des Groupes, ce que je suis en train de faire (j'ai fait un post sur Mikhail GROMOV et ses travaux sur la TGG).
Roger PENROSE a aussi publié très tôt dans sa carrière des travaux sur les pavages (de type diédral) et les symétries (groupes cycliques).

Je pense que la représentation géométrique la plus efficace des groups finis est le graphe Cayley et le concept de générateurs.
C'est extrêmement généraliste et s'applique à une variété de groupes très étendu tant qu'il y a des symétries et donc des invariants de groupes.
J'ai découvert qu'il y avait des applications en Chimie Moléculaire (Stéréochimie).

Groupe diédral fini d'ordre 2n:
https://demonstrations.wolfram.com/DihedralGroupNOfOrder2n/

Un résumé du CNRS:
https://images.math.cnrs.fr/Un-peu-de-geometrie-des-groupes.html?lang=fr

Un PAVE exhaustif mais thématique :
https://imag.umontpellier.fr/~haettel/TGG.pdf

Bonne nuit,

Riemann_lapins_cretins

Merci beaucoup, c'est très intéressant !

N'ayant pas fait de maths ou presque en deux ans je me replonge doucement dans Arnaudies/Berlin pour le plaisir (mon livre préféré de maths, avec Analyse fonctionnelle de Daniel Li et le Colmez).
Je piocherai un peu plus tard après avoir reformaté mon cerveau en algèbre.

purple

Il est sympa ton problème, je ne le connaissais pas, j'aurais bien aimé qu'on me donne ce genre de chose à l'époque où on m'a enseigné les actions de groupes.
Éléments de géométrie : actions de groupes de R. Mneimné pourrait te plaire, surtout parce que tu as une idée bien précise de ce que tu cherches donc tu sauras t'y retrouver. Parfois ça vole un peu haut à mon goût mais c'est tellement dense qu'on trouve facilement de quoi se nourrir.

GaBuZoMeu

Bonjour,

Il y a une flopée de problèmes de ce genre, un des plus connus étant le coloriage d'un collier de perles.
On peut voir par exemple : 'Ras-le-bol du collier de perles".

Riemann_lapins_cretins

Oh merci, c'est parfait et les anecdotes d'agreg c'est toujours rigolo !