Forum de mathématiques - Bibm@th.net

DavidRC5

Membre

Inscription : 23-10-2024

Messages : 2

Méthode pour aborder un problème de dénombrement et combinatoire

Bonjour à tous ceux qui pourraient lire cette discussion,

Actuellement en licence de maths j'ai un cours de combinatoire et théorie des graphes. Pour la partie combinatoire j'ai vraiment du mal à comprendre quel critère appliquer en fonction de l'exercice. Je sais pas s'il faut compter des applications, utiliser un principe de dénombrement, une permutation ou les nombres de Stirling, coefficients binomiaux, etc.
En voyant les corrigé des TDs ça parait hyper logique mais je n'ai aucune idée de comment raisonner dans un exercice de ce type, il y a-t-il des méthodes qui peuvent être utiles pour bien comprendre le besoin de chaque exercice?
J'essaye d'appliquer les théories vues en cours mais à chaque fois je sens que j'arrive à des réponses uniquement en "tâtonnant", est-ce que je dois juste continuer à faire des exercices et ça viendra éventuellement ou il y a une démarche qui permet de mieux comprendre les sujets? J'avoue me sentir un peu perdu et j'apprécierais fortement d'avoir des conseils sur comment aborder ce genre d'exercices.

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Méthode pour aborder un problème de dénombrement et combinatoire

bonjour,

En nous donnant un exemple d'exercice de niveau moyen auquel tu es confronté, et qui te poses des difficultés, on pourra mieux t'aider.
La théorie des graphes fournissant des théorèmes assez pointus (ne serait-ce qu'en terme d'énoncés parfois) , merci de nous adjoindre si l'exercice est très spécialisé les 2 ou 3 résultats principaux vus en cours qui peuvent être utiles.
Sinon, de manière générale, une approche possible est de comprendre les choses sur des petits ordres du graphe en essayant d'en tirer les conclusions les plus utiles.
En enlevant une hypothèse majeure qui aboutit à faire capoter le résultat, ça peut parfois aider à la résolution.

A.

DavidRC5

Membre

Inscription : 23-10-2024

Messages : 2

Re : Méthode pour aborder un problème de dénombrement et combinatoire

Bonjour bridgslam, merci pour ta réponse

voici un style d'exercice qu'on a vu en TD avec ça correction :

Exercice 1.
(a) Quel est le nombre de suites contenant au moins un 6 qu’on peut obtenir en jetant dix
fois de suite un dé ?
(b) De combien de manières distinctes n personnes peuvent-elles être positionnées dans une
file ? et assises autour d’une table ?
(c) Combien de mots de n lettres (sans répétition) peut-on écrire avec l’alphabet {a1, a2, . . . ,
an} de façon que a1 et a2 soient côte-à-côte ? Et de façon que a1 soit placé à gauche de
a2 ?

Voici la solution qui nous est donné :

Solution 1.
(a) Le nombre de suites contenant au moins une fois 6 est égal au nombre de suites possibles
moins le nombre de suites sans 6. Il vaut donc 6^10 − 5^10.
(b) Il y en a respectivement n! et n!/n = (n − 1)!. Les placer sur une file revient à choisir une permutation. Pour les placer autour une table (en considérant les rotations comme étant la même distribution) on peut d’abord fixer la position de la première personne,
et puis il ne reste que distribuer une permutation des autres personnes.
(c) On trouve 2(n − 1)! et "2 parmi n" * (n − 2)! = n!/2.
Pour le premier cas, si a1 précède a2 et ils sont consécutifs, on a vu dans un exercice que le nombre de possibilités est (n−1)!. Le nombre de possibilités quand a2 précède a1 et ils sont consécutifs est aussi (n − 1)! pour le même argument. Le principe d’addition
nous donne que le nombre total 2(n − 1)!.
Pour le cas où a1 est à gauche de a2 mais ils ne sont pas forcement consécutifs, on remarque qu’il en y a autant que de cas ou a1 est à droite de a2 (car échanger leur position donne une bijection). Comme ces deux familles forment une partition de l’ensemble de
tous les n! mots, on en déduit que chacune des deux familles a cardinal n!
2 . (Une autre façon de trouver cette formule est de choisir d’abord les positions de a1 et a2, pour ce qu’on a "2 parmi n"
choix, et ensuite placer les autres lettres, on a (n − 2)! possibilités.)

Je comprends la correction mais je ne sens pas avoir l'intuition pour savoir quand je dois faire une permutation ou une combinaison, ça aide pas beaucoup que je suis étudiant à distance donc j'ai juste accès aux polycopiés des cours et les fiches de td avec leur correction mais clairement ce serait plus facile de pouvoir poser la question directement à un prof et ils ne sont pas forcément très réactifs par mail.

Dernière modification par DavidRC5 (23-12-2024 09:00:44)

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Méthode pour aborder un problème de dénombrement et combinatoire

Bonjour,

Merci pour les précisions.
En l' occurrence il s'agit ici de dénombrements.
Vis à vis des graphes, le plus souvent ils peuvent servir à effectuer des dénombrements difficiles, mais on peut aussi dénombrer des possibilités liées au graphes en soi : chemins, sous-graphes vérifiant telle propriété etc

A vrai dire il n'y a pas de recettes miracle pour trouver les réponses, mais si on est perdu,  des essais avec des valeurs particulières assez petites des paramètres permettent en général de bien saisir la situation.

Quelques observations:

- le premier exemple te montre qu'il est parfois plus simple de dénombrer l'ensemble des situations contraires, puis de retomber sur ses pieds par différence
- pour les convives autour d'une table, on peut dire aussi qu'il y a n! cas, mais qu'il faut diviser par n si seules les positions relatives importent, puisqu'on doit considérer qu'on peut grouper exactement par  n les permutations qui sont équivalentes, donc ne comptent que pour 1.

Tu peux t' exercer sur des variantes : avec n couples HF,

- une personne particulière ne veut pas occuper telle place
- chaque convive veut avoir quelqu'un du sexe opposé en face de lui
- en alternant les sexes côte à côte
- chacun veut être voisin de son conjoint
- alternance HF,  mais aucun n'est à côté de son conjoint
- aucun à côté de son conjoint, sans obliger l'alternance des sexes

etc

Ce genre d'exercice permet de s'entraîner à bien visualiser des situations plus ou moins compliquées.

A.

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : Méthode pour aborder un problème de dénombrement et combinatoire

Bonjour,
Correction:

Comme ces deux familles forment une partition de l’ensemble de tous les n! mots, on en déduit que chacune des deux familles a cardinal n!/2

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Méthode pour aborder un problème de dénombrement et combinatoire

Re-bonjour,

Sinon un abord un peu plus mathématique (pour éviter les "on voit que..." ) pour votre question de table:
parmi les n! dispositions (d) , si on dit que d R d' ssi une rotation autour de la table échange d en d' , R est une relation d'équivalence.
Chaque classe contient n éléments. La question devient limpide puisqu'on veut dénombrer le nombre de classes.
En fait on a un résultat de théorie des groupes plus général (formule de Burnside ) qui permet de se sortir d'affaire quand on regarde ce qui est équivalent
quand on fait agir un groupe sur un ensemble.
Par exemple si vous cherchez à calculer (directement)  le nombre de pièces d'un jeu de triomino ( les pièces triangulaires diffèrent par la valeur dans chaque angle ), vous aurez des redondances inutiles en jouant sur toutes les possibilités coin par coin, du fait d'équivalences possibles à symétries ou rotations près des pièces.
La prise en compte du groupe D3 du triangle équilatéral fournit directement le dénombrement en appliquant la formule de Burnside.

▼les détails

Pour les triominos, on fait agir D3 ( 6 éléments) sur tous les triplets, Fix(id) a $6^3 $ éléments, chacune des 3 symétries a un fixateur à $ 6^2 $éléments, chacune des 2 rotations a un fixateur à 6 éléments:  $1/6( 6^3 + 3.6^2 + 2.6 ) = 56$ , le nombre de pièces du jeu ( les points permis vont de 0 à 5, l'ordre est croissant(large) en sens horaire). Le compte y est...

J'avais posté cette petite analyse sur un site de vidéos de maths, car l'auteur présentait la chose sur les dominos, où un dénombrement sans Burnside est trivial.
J'avais pensé que se pencher sur les pièces à 3 valeurs au lieu de 2 pour les dominos  mettait plus en valeur l'intérêt d'action de groupe.

Idem pour des questions en 3d , coloriages de cubes par exemple, ou de colliers de perles colorées etc.

En résumé, quelques conseils personnels pour progresser:

- commencer par des petites questions simples, si possible en cherchant plusieurs méthodes de résolution
- augmenter très graduellement la complexité des questions
- essayer dans la mesure du possible de se ramener à des dénombrements classiques ( parfois il suffit de coder le problème pour le simplifier, avec un peu d'imagination)
- parfois si le pb est difficile, on peut l'aborder par récurrence, quitte à trouver a posteriori le "pourquoi du comment"
- quelques problèmes donnent des solutions avec une approche géométrique ( nombre de chemins etc ) ou algébrique
- des résultats classiques sont souvent utiles: le crible de Poincaré, les nombres de Catalan (que l'on retrouve dans une multitude de questions)

On doit placer autour d’une table ronde un groupe de 2n personnes, n hommes et n femmes, qui constituent n
couples. Combien existe-t-il de dispositions . . .
1. au total ?
2. en respectant l’alternance des sexes ?
3. sans séparer les couples ?
4. en remplissant les deux conditions précédentes ?

On considérera cette fois que deux dispositions qui diffèrent par rotation ne sont pas identiques
( par exemple Pierre sera près de la cheminée, Pierrette près de la porte, jean près de la fenêtre etc les places ne sont donc pas équivalentes )

Enfin il est normal d'avoir des difficultés de prime abord, elles s'estompent en faisant des exercices, il faut persévérer.

Bon courage

A.

Dernière modification par bridgslam (23-12-2024 19:58:47)

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : Méthode pour aborder un problème de dénombrement et combinatoire

Les triominos sont-ils bifaces ? Il ne me semble pas, et donc une tuile est différente de sa symétrique. On ne compte pas alors les orbites pour $D_3$, mais juste pour $C_3$.

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Méthode pour aborder un problème de dénombrement et combinatoire

Bonjour,

Les pièces en parcourant les coins (en sens horaire ou anti-horaire je ne sais plus)

000, 111, 222, 333, 444, 555, 001, 112, 223, 334, 445, 002, 113, 224, 335, 455, 003,
114, 225, 344, 004, 115, 233, 345, 005, 122, 234, 355, 011, 123, 235, 012, 124, 244,
013, 125, 245, 014, 133, 255, 015, 134, 022, 135, 023, 144, 024, 145, 025, 155, 033,
034, 035, 044, 045, 055

Voir le commentaire A sous la video de Gille Bailly-Maitre
https://www.youtube.com/watch?v=mRsg2lqEjPM

Sauf erreur c'est bien D3 qui joue, il donne d'ailleurs le bon nombre de pièces du jeu classique
avec des valeurs de 0 à 5 dans les coins.
Il faut bien utiliser les symétries car dans l'absolu on aurait, par exemple,  plusieurs 0 4 4 ( 3 en fait, selon
le choix de 0) équivalents à 1 seule pièce réelle du jeu par symétrie entre les  4.
Et par exemple (0,1,2) et (1,0,2) ne sont équivalents sous l'effet d'aucune rotation, mais bien
par une symétrie d'axe passant par la position du 2 dans ce triomino.

Alain

Dernière modification par bridgslam (23-12-2024 17:30:15)

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Méthode pour aborder un problème de dénombrement et combinatoire

....

Cela revient si on préfère à dénombrer le nombre de suites croissantes au sens large ( n,m ,r) parmi $[0;5]^3$

Pour ceux qui ne connaissaient pas ce jeu:

Bonne soirée
A.

Dernière modification par bridgslam (23-12-2024 19:53:03)

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : Méthode pour aborder un problème de dénombrement et combinatoire

D'accord, je ne connaissais pas la contrainte qu'il y a un parcours croissant des sommets dans le sens des aiguilles d'une montre. Cela revient donc effectivement à compter les suites croissantes de trois entiers entre 0 et 5, ou encore les suites strictement croissantes de trois entiers entre 0 et 7 (en ajoutant 1 au 2e et 2 au 3e) ce qui revient à compter les sous-ensembles de trois entiers entre 0 et 7, ce qui fait le coefficient binomial $C_8^3=56$. Ça me semble plus rapide que de faire intervenir Burnside.

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Méthode pour aborder un problème de dénombrement et combinatoire

Bonsoir,

Bien-sûr, mais ce n'était pas l'esprit de la chose:
je souhaitais montrer qu'au lieu d'utiliser Burnside pour un dénombrement (encore plus simplissime aussi directement )de pièces de dominos, à l'instar de Gilles Bailly-Maître dans sa video qui illustre le th. de Burnside, c'était un peu plus amusant de faire jouer un autre  groupe pour dénombrer les pièces d'un jeu voisin mais un peu plus consistant en structure à se mettre sous la dent, tout simplement, que des dominos.

Ce dénombrement est effectivement classique par ailleurs par voie directe, comme tu le mentionnes.
Je crois me souvenir que c'était proposé en classes prépas, comme bon exercice de dénombrement.
Académiquement (si je puis dire) il est à mon sens amusant de constater qu'un groupe diédral se cache derrière.
En plus un béotien qui ouvre une boîte de ce jeu pour la première fois n'y voit pas forcément d'emblée des suites croissantes en sens horaire, mais est plutôt impressionné par l'aspect triangulaire avec des points éparpillés dans les coins...

A.

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Méthode pour aborder un problème de dénombrement et combinatoire

Bonjour,

Apparemment, d'après l'image, la graphie des chiffres est telle
qu'ils ont leur représentation habituelle quand leur  coin  est vers  le bas (sans incidence pour 0 évidemment vu sa symétrie, et si les points allaient jusqu'à 9, que penser de 6 et de 9...).

Je pense qu'une variante du jeu avec de petites figures géométriques avec ou sans symétrie, à la place des chiffres, et  pouvant être orientées différemment selon les pièces,  doit fournir du grain à moudre côté dénombrement, où cette fois une action de groupe devient une nécessité, les choses prenant une tournure résolument géométrique et transformiste.

A creuser...

Bon réveillon
A.

Dernière modification par bridgslam (24-12-2024 14:00:31)