Inscription / Connexion Nouveau Sujet
Niveau LicenceMaths 2e/3e a
Partager :

Analyse combinatoire

Posté par
Karting
29-05-22 à 00:23

Bonjour, Combien y a t'il de façon de séparer 8 personnes en 3 groupes ?

Posté par
Sylvieg Moderateur
re : Analyse combinatoire 29-05-22 à 07:55

Bonjour,
Qu'as-tu essayé ?

Posté par
Karting
re : Analyse combinatoire 29-05-22 à 12:37

Bonjour j'ai essayé ça
(3^8-(3*2^8)+3)/(3!)
Comme si on a 8 qui doit choisir entre 3 groupe G1 G2 G3.. En soustrayant 3*2^8 je pensais éliminer le cas où un des 3 groupes ne contenait aucune personne mais je pensais aussi qu'il y a 3 cas que je compte deux fois c'est pourquoi j'ai fais le +3 et pour éliminer l'ordre de G1 G2 G2 j'ai divisé par 3!
Voilà mais je doute un peu de ma réponse

Posté par
carpediem
re : Analyse combinatoire 29-05-22 à 13:37

salut

8 = 1 + 1 + 6 = 1 + 2 + 5 = 2 + 2 + 4 = 2 + 3 + 3

...

Posté par
GBZM
re : Analyse combinatoire 29-05-22 à 15:28

Bonjour,

On parle de huit personnes, on peut penser qu'elles sont distinguables entre elles. Dans ce cas, la réponse de carpediem ne convient pas.
Ta réponse, Karting, est plus sensée. Tu comptes en fait les surjections d'un ensemble à 8 éléments (les personnes) sur un ensemble à 3 éléments (les groupes), en utilisant la formule du crible de Poincaré, et ensuite tu divises par le nombre de permutations des groupes, puisque leur ordre n'intervient pas. Tu peux calculer explicitement le quotient et vérifier que c'est bien un entier.
Tu peux faire une autre vérification en utilisant tout de même le décompte de carpediem (en ajoutant 1+3+4 à la liste). Il faut répartir les huit personnes entre les trois paquets, et tenir aussi compte des permutations de groupes de même nombre de personnes. La méthode que tu as employée est plus simple.

Posté par
carpediem
re : Analyse combinatoire 29-05-22 à 16:06

GBZM : oui un oubli dans l'écriture des différentes décompositions ...

GBZM @ 29-05-2022 à 15:28

Bonjour,

On parle de huit personnes, on peut penser qu'elles sont distinguables entre elles. Dans ce cas, la réponse de carpediem ne convient pas.

Tu peux faire une autre vérification en utilisant tout de même le décompte de carpediem (en ajoutant 1+3+4 à la liste). [...]

La méthode que tu as employée est plus simple. une méthode ? ... ou simplement l'application d'une formule qu'il faut connaitre ...

alors ma méthode : elle convient ou elle ne convient pas ?

elle est certainement plus longue et plus "fastidieuse" en particulier à devoir être attentif à ne pas compter deux fois des paires de groupes de même cardinal ... mais elle convient !!!

et surtout elle est naïve, personnelle et exige un vrai effort personnel plutôt que la simple recopie et application d'une formule d'un autre ...

même si bien sûr il est bon de savoir et pouvoir s'enrichir de savoirs ...

Posté par
GBZM
re : Analyse combinatoire 29-05-22 à 16:32

Ne te vexe pas, carpediem !
Déjà, ça partait mal, tu avais oublié le 1+3+4.
Ensuite, Karting avait fait un calcul tout à fait correct et assez bien justifié, je ne vois pas pourquoi tu lui suggères autre chose, avec en plus l'ambiguïté de savoir si tu ne comptes pas seulement les partitions de l'entier 8 en trois entiers.
Enfin, il s'agit bien d'une méthode importante en analyse combinatoire pour compter le cardinal d'une réunion, appliquée ici pour compter les surjections.
Karting compte les applications d'un ensemble à 8 éléments dans un ensemble de 3, il enlève la somme des cardinaux des ensembles d'applications qui loupent un élément donné, et il ajoute la somme des cardinaux des ensembles d'applications qui loupent deux éléments donnés (elles ont été enlevées deux fois).

Posté par
AitOuglif
re : Analyse combinatoire 29-05-22 à 16:53

Bonjour
Je connais plusieurs méthodes de ce problème classique. Mais je me suis évertué à essayé une autre piste du cas général et je ne comprends pas pourquoi je ne parviens pas à terminer. J'appelle r(n,p)(ranger n personnes distinguables dans p groupes).
Je constitue un premier groupe de k personnes(je verrai après dans quoi est k). Il y a \binom {n}{k} possibilités. Ensuite, il me reste à ranger n-k personnes dans p-1 groupes, ce qui fait r(n-k,p-1) possibilités. Il me reste à sommer le produit \binom{n}{k}r(n-k,p-1) pour k allant de 1 à n-p+1(les groupes restants doivent avoir au moins 1 personne).
Bref, je ne sais pas si mon truc peut fonctionner?

Posté par
AitOuglif
re : Analyse combinatoire 29-05-22 à 16:54

Je précise que j'essaie de traiter le problème de manière récursive.

Posté par
GBZM
re : Analyse combinatoire 29-05-22 à 17:00

AitOuglif, ta récurrence ne va pas parce qu'elle fait jouer un rôle particulier au premier groupe. Ce n'est pas grave s'il n'y a pas d'autre groupe de même cardinal, mais si c'est la cas tu compteras deux fois la même répartition.

Posté par
GBZM
re : Analyse combinatoire 29-05-22 à 17:01

(deux fois ou plus)

Posté par
carpediem
re : Analyse combinatoire 29-05-22 à 17:23

GBZM : non je ne suis pas vexé ...

je te chipotais sur ton "non mais oui" au sujet de ma réponse ...

j'ai répondu cela parce que

Karting @ 29-05-2022 à 12:37

j'ai essayé ça  [...] mais je doute un peu de ma réponse
et je lui proposais simplement une autre voie pour retrouver (ou pas) son résultat en comptant (enfin avec un oubli) les différentes possibilités de cardinal des trois groupes ...

il ne me semble pas que ce soit si compliqué que ça bien que plus long j'en conviens ...
et merci du rappel du non de la formule (crible de Poincaré)

Posté par
AitOuglif
re : Analyse combinatoire 29-05-22 à 17:25

oui je vois en effet, merci GBZM.

Posté par
Karting
re : Analyse combinatoire 29-05-22 à 18:30

Merci à tous pour vos réponses

Posté par
Sylvieg Moderateur
re : Analyse combinatoire 31-05-22 à 11:42

Bonjour,
Un peu de disponibilité aujourd'hui pour transmettre mes réflexions.
Au départ, j'ai trouvé bizarre un exercice niveau terminale posé niveau licence.
J'ai vite compris que ce n'était pas si simple, mais j'ai persévéré avec des outils niveau terminale.
Même démarche que carpediem (mais sans oublier un cas ).
Pas vraiment agréable, mais on y arrive.
Ta réponse, Karting, ne me semblait pas convaincante (à toi non plus d'ailleurs) ; mais elle donne le même résultat.
Il me semble que tu as plus ou moins redémontré la formule du crible dans ce cas particulier.
Mais tes explications n'étaient pas d'une clarté époustouflante

Posté par
AitOuglif
re : Analyse combinatoire 31-05-22 à 13:50

Bonjour Sylvieg
Je me demande s'il on ne doit pas distinguer(hihih) les cas (pour le problème "ranger p machin dans n trucs"):
- machins et trucs discernables
- machins discernables et trucs indiscernables , et vice versa
- machins et trucs indiscernables

Par exemple, il me semble que le nombre de surjections d'un ensemble à p éléments dans un ensemble à n éléments correspond au premier cas.
Après, malheureusement je suis très mauvais en combinatoire.

Posté par
AitOuglif
re : Analyse combinatoire 31-05-22 à 14:10

Par exemple, si on me dit de répartir 8 personnes dans 3 salles. Pour dénombrer les possibilités, je dis qu'on cherche les 8-uplets de l'ensembles \{salle1, salle2, salle3\}. Un 8-uplet satisfaisant pourrait être par exemple (salle1, salle1, salle3, salle3, salle1, salle2, salle2, salle1) qui est dans \{salle1, salle2, salle3\}^8. Cela fait 3^8...

Posté par
GBZM
re : Analyse combinatoire 31-05-22 à 14:22

Oui, tu comptes le nombre d'applications d'un ensemble à 8 éléments dans un ensemble à 3 éléments. Et alors ?

Posté par
AitOuglif
re : Analyse combinatoire 31-05-22 à 14:28

Et donc, quelle différence avec le problème de Karting :
"Combien y a t'il de façon de séparer 8 personnes en 3 groupes ?"?
L'indiscernabilité des groupes?

Posté par
Sylvieg Moderateur
re : Analyse combinatoire 31-05-22 à 14:39

L'indiscernabilité des groupes : oui.
Mais aussi aucun groupe vide. Exemple :
(salle1, salle1, salle3, salle3, salle1, salle3, salle1, salle1) ne convient pas.

Posté par
AitOuglif
re : Analyse combinatoire 31-05-22 à 14:41

Ah oui merci Sylvieg, benh oui, cela voudrait dire qu'on n'a pas respecté le problème(répartir sur les 3 salles, et non sur 2). Merci Sylvieg et GBZM!

Posté par
Sylvieg Moderateur
re : Analyse combinatoire 31-05-22 à 15:01

De rien
Et pour ton idée de récurrence, j'ai trouvé ceci :

La dernière modif date du 26 mai !
Il y a aussi un triangle à la fin qui contient la réponse de l'exercice.

Posté par
AitOuglif
re : Analyse combinatoire 31-05-22 à 15:15

Ah oui très intéressant! Merci beaucoup !



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1541 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !