Combinaisons, Arrangements, Permutations
Il y a un truc avec lequel je m'embrouille souvent en combinatoire, c'est les arrangement, combinaisons et permutations. En fait, je me suis rendu compte que j'avais du mal à savoir exactement quoi utiliser quand parce que je n'ai pas de définition claire et nette de ces objets.
J'ai fait un tour sur le cours de combinatoire de la Wikiversité et ça a répondu à un certain nombre de mes questions, mais pas toutes.
Ils distinguent six objets différents : les permutations, arrangements et combinaisons, avec et sans répétitions.
1) Les arrangements sans répétitions : ils notent ça $A_n^k$ et on peut définir ça comme le cardinal de l'ensemble des injections de $\{1,...,k\}$ dans $\{1,...,n\}$. Là j'ai une définition claire, après il faut juste encore démontrer que le nombre de tirages sans remise et tenant compte de l'ordre de $k$ éléments parmi $n$ est bien égal à ça. Faisable.
2) Les arrangements avec répétitions : c'est le cardinal de l'ensemble des applications de $\{1,...,k\}$ dans $\{1,...,n\}$. Tranquille. C'est censé correspondre aux tirages avec remise et tenant compte de l'ordre, je pense pouvoir démontrer que c'est ça.
3) Les permutations sans répétitions : J'aime bien définir ça en disant que je note $n!$ le cardinal du groupe symétrique $\mathfrak{S}_n$, et après en déduire que $0!=1$ (donc que c'est pas une "convention pratique" mais une conséquence logique) et que pour $n$ non nul, on a $n! = \displaystyle \prod_{k \in \{1,...,n\}}k$. Ensuite, le côté combinatoire des permutations sans répétitions, je peux comprendre.
Jusque-là, je m'en sors. Maintenant ça devient compliqué.
4) Les permutations avec répétitions : On veut que ce nombre soit égal au nombre d'anagrammes d'un mot, en tenant compte des éventuelles lettres qui apparaissent plusieurs fois. Voir ici. Le souci que j'ai, c'est que j'aimerais définir les permutations avec répétitions comme un certain type d'applications, comme on l'a fait avant (injections, applications, bijections) dans les trois premiers cas. Et je ne vois pas trop comment on fait ça, quels ensembles choisir.
5) Les combinaisons sans répétitions : c'est le coefficient binomial $C_n^k$, je le connais bien. Je sais que ça doit correspondre au nombre de parties à $k$ éléments dans un ensemble à $n$ élémens, donc on peut définir ça comme les parties de $\{1,...,n\}$ qui sont en bijection avec $\{1,...,k\}$. Donc il faut encore compter des bijections, mais de quoi dans quoi ? Je m'embrouille un peu.
6) Les combinaisons avec répétitions : Rien qu'à la définition qu'ils en donnent, j'ai du mal à voir le concept.
Je précise aussi un truc. J'ai du mal avec les multi-ensembles, je pense qu'il faudra passer par ça aussi...
Donc voilà. Mon objectif, c'est des définitions propres (en termes d'applications entre des ensembles) des machins 4) 5) et 6). Je n'ai vraiment trouvé nulle part de définitions bien carrées de ces objets. Merci de m'aider avec ça !
J'ai fait un tour sur le cours de combinatoire de la Wikiversité et ça a répondu à un certain nombre de mes questions, mais pas toutes.
Ils distinguent six objets différents : les permutations, arrangements et combinaisons, avec et sans répétitions.
1) Les arrangements sans répétitions : ils notent ça $A_n^k$ et on peut définir ça comme le cardinal de l'ensemble des injections de $\{1,...,k\}$ dans $\{1,...,n\}$. Là j'ai une définition claire, après il faut juste encore démontrer que le nombre de tirages sans remise et tenant compte de l'ordre de $k$ éléments parmi $n$ est bien égal à ça. Faisable.
2) Les arrangements avec répétitions : c'est le cardinal de l'ensemble des applications de $\{1,...,k\}$ dans $\{1,...,n\}$. Tranquille. C'est censé correspondre aux tirages avec remise et tenant compte de l'ordre, je pense pouvoir démontrer que c'est ça.
3) Les permutations sans répétitions : J'aime bien définir ça en disant que je note $n!$ le cardinal du groupe symétrique $\mathfrak{S}_n$, et après en déduire que $0!=1$ (donc que c'est pas une "convention pratique" mais une conséquence logique) et que pour $n$ non nul, on a $n! = \displaystyle \prod_{k \in \{1,...,n\}}k$. Ensuite, le côté combinatoire des permutations sans répétitions, je peux comprendre.
Jusque-là, je m'en sors. Maintenant ça devient compliqué.
4) Les permutations avec répétitions : On veut que ce nombre soit égal au nombre d'anagrammes d'un mot, en tenant compte des éventuelles lettres qui apparaissent plusieurs fois. Voir ici. Le souci que j'ai, c'est que j'aimerais définir les permutations avec répétitions comme un certain type d'applications, comme on l'a fait avant (injections, applications, bijections) dans les trois premiers cas. Et je ne vois pas trop comment on fait ça, quels ensembles choisir.
5) Les combinaisons sans répétitions : c'est le coefficient binomial $C_n^k$, je le connais bien. Je sais que ça doit correspondre au nombre de parties à $k$ éléments dans un ensemble à $n$ élémens, donc on peut définir ça comme les parties de $\{1,...,n\}$ qui sont en bijection avec $\{1,...,k\}$. Donc il faut encore compter des bijections, mais de quoi dans quoi ? Je m'embrouille un peu.
6) Les combinaisons avec répétitions : Rien qu'à la définition qu'ils en donnent, j'ai du mal à voir le concept.
Je précise aussi un truc. J'ai du mal avec les multi-ensembles, je pense qu'il faudra passer par ça aussi...
Donc voilà. Mon objectif, c'est des définitions propres (en termes d'applications entre des ensembles) des machins 4) 5) et 6). Je n'ai vraiment trouvé nulle part de définitions bien carrées de ces objets. Merci de m'aider avec ça !
Réponses
-
Du point de vue dénombrement, tu peux voir une permutation d'un ensemble $E$ à $n$ éléments comme une bijection de $\{1,\ldots,n\}$ sur $E$. Bien sûr, pour étudier le groupe des permutations, ce n'est pas une bonne façon de voir les choses !
Maintenant suppose que tu as une relation d'équivalence $\sim$ sur ton ensemble $E$ à $n$ éléments, avec des classes d'équivalences de cardinaux $k_1,\ldots, k_r$ (avec les $k_i>0$ de somme $n$). Une permutation avec répétition de $(E,\sim)$ est une classe d'équivalence de bijections de $\{1,\ldots,n\}$ sur $E$, où deux bijections $f$ et $g$ sont équivalentes si et seulement si elles induisent la même application de $\{1,\ldots,n\}$ sur $E/{\sim}$.
(Si tu veux penser en termes de multi-ensemble, tu peux voir $E/{\sim}$ comme un multi-ensemble où la multiplicité de chaque classe d'équivalence est son cardinal. Une permutation avec répétition est alors une application de $\{1,\ldots,n\}$ sur $E/{\sim}$ telle que le nombre d'antécédents de chaque élément de $E/{\sim}$ soit égal à sa multiplicité.) -
Poursuivons :
1) Combinaison sans répétition de $k$ éléments parmi l'ensemble $X$ à $n$ éléments : c'est une classe d'équivalence d'injections de $\{1,\ldots,k\}$ dans $X$, où deux injections $f$ et $g$ sont équivalentes si et seulement s'il existe une permutation $\sigma$ de $\{1,\ldots,k\}$ telle que $g=f\circ \sigma$.
1) Combinaison avec répétition de $k$ éléments parmi l'ensemble $X$ à $n$ éléments : c'est une classe d'équivalence de fonctions de $\{1,\ldots,k\}$ dans $X$, où deux fonctions $f$ et $g$ sont équivalentes si et seulement s'il existe une permutation $\sigma$ de $\{1,\ldots,k\}$ telle que $g=f\circ \sigma$.
3) L'ensemble des combinaisons avec répétition de $k$ éléments parmi $X$ est en bijection avec l'ensemble des fonctions $\nu : X\to \mathbb N$ telles que $\sum_{x\in X} \nu(x)=k$ ; la fonction $X\to \mathbb N$ associée à une combinaison avec répétition représentée par la fonction $f:\{1,\ldots,k\}\to X$ est celle qui à $x\in X$ fait correspondre son nombre d'antécédents par $f$. Parmi ces fonctions $X\to \mathbb N$, celles qui correspondent aux combinaisons sans répétition sont bien sûr celles qui prennent leurs valeurs dans $\{0,1\}$. -
Une suggestion : the twelvefold way.
-
@Math Coss : où vois-tu les permutations avec répétition dans le "twelvefold way" ?
@babsgueye : ne parle pas à la place de Homo Topi, même s'il a délaissé le sujet qu'il a lancé. -
Il n'y a pas. Ça me paraît pourtant un point de vue utile, même s'il ajoute des catégories à celles que propose HomoTopi : on fixe deux ensembles (disons $N$ et $X$ ; on a le choix entre 1) trois types d'applications (applications, injections, surjections) ; 2) compter à permutation près ou pas à la source ; 3) compter à permutation près ou pas au but.
Pour intégrer les permutations avec répétitions, on peut introduire le sous-groupe $H$ du groupe des permutations de $X$ qui permutent les lettres du mot initial que l'on veut identifier. Dans le cas de "cellule", on va prendre $N=\{1,\dots,8\}$ (longueur du mot initial), $\newcommand{\c}{\mathrm{c}}\newcommand{\e}{\mathrm{e}}\newcommand{\l}{\mathrm{l}}\newcommand{\u}{\mathrm{u}}X=\{\c,\e_1,\l_1,\l_2,\u,\l_3,\e_2\}$ et $H$ le sous-groupe des permutations qui stabilisent $\{\c\}$, $\{\e_1,\e_2\}$, $\{\l_1,\l_2,\l_3\}$ et $\{\u\}$.
Les permutations avec répétitions sont les bijections de $N$ dans $X$ à permutation par un élément de $H$ près (c'est intermédiaire entre les bijections de $N$ dans $X$ à rien près – cardinal $8!$ et les bijections de $N$ dans $X$ à permutation de $X$ près – cardinal $1$). -
Peux-tu m'expliquer la différence de point de vue entre le "twelvefold way" et la définition que j'ai donnée pour les combinaisons et les combinaisons avec répétitions.Ça me paraît pourtant un point de vue utile
On a vu que les permutations avec répétition ne rentrent pas dans le "twelvefold way". -
L'intérêt de la présentation twelvefold, c'est le package. Il donne un point de vue uniforme sur un grand nombre de dénombrements qui semblent disparates au premier abord.
Si on généralise un peu en se donnant deux ensembles $N$ et $X$ (ou $E$), un sous-groupe $K$ de $\mathfrak{N}$ et un sous-groupe $H$ de $\mathfrak{X}$, on peut vouloir calculer les fonctions (resp. injections, surjections) de $N$ dans (sur) $X$ à pré- ou post-composition par un élément de $K$ ou $H$ près. Quand $K$ est trivial et $H$ est le stabilisateur d'une partition de $X$, on code les permutations avec répétitions.
Sinon, on m'a montré ça il y a un peu plus d'un an à peine : je m'en suis passé jusque là mais je trouve plaisant l'uniformisation des problèmes que cela permet, même si ce n'est pas l'alpha et l'oméga de la combinatoire. Je ne comprends pas pourquoi ce post te dérange autant. Le twelvefold-way montre au moins une chose, c'est que la typologie des problèmes de base de combinatoire adoptée par la Wikiversité n'est pas universelle. -
Ton post ne me dérange pas, je questionne sa pertinence, c'est tout (mes raisons sont assez claires d'après ce que j'ai déjà écrit, je pense). Bon, de toutes façons Homo Topî semble s'être désintéressé du sujet.
-
Moi ce que je comprends pas ici, c'est peut être élémentaire, mais c'est la notion de combinaison avec répétition, sa différence avec une combinaison sans répétition..
On sait qu'une combinaison $\binom{n}{k}$ est les choix de $k$ éléments parmi $n$. C'est quoi la formule d'une combinaison avec répétition ? C'est quoi la différence avec une combinaison sans répétition ? -
Les définitions ont été données : il suffit de les lire et de faire l'effort de les comprendre (ça demande un petit effort).
Compter les combinaisons avec répétition de $k$ objets parmi $n$, c'est un marronnier du forum. Encore une fois pour babsgueye :
On compte les fonctions $\nu : \{1,\ldots,n\}\to \mathbb N$ telles que $\sum_{i=1}^n \nu(i)=k$ (cf mon message plus haut). On peut donner une telle fonction par la liste de ses $n$ valeurs, qui sont $n$ entiers naturels de somme $k$. Par exemple pour $n=7$ et $k=9$ :
[2,0,1,4,1,1,0]
que l'on peut représenter graphiquement
O O | | O | O O O O | O | O |
une liste de $n-1+k= 15$ symboles dont $n-1$ sont des | et k des O.
C'est facile à compter de ce point de vue. -
Alors, non, je ne me suis pas désintéressé du sujet du tout.
Je suis quelqu'un qui a beaucoup de mal à rester concentré sur un seul sujet très longtemps, certains auront peut-être remarqué que je poste souvent plusieurs questions qui n'ont rien à voir entre elles en même temps sur le forum.
J'avais un peu de mal avec les premières réponses de GBZM, et comme là prochainement j'ai beaucoup de choses très très importantes à faire dans ma vie professionnelle, j'ai préféré laisser ça de côté avant de m'y remettre sérieusement (et en attendant, j'ai continué à regarder les fils que j'ai lancés où j'ai moins de difficultés à comprendre les choses rapidement).
N'allez pas croire que je ne suis pas reconnaissant de l'aide qu'on me donne ! :-(
@babs : le deuxième message de GBZM est exactement ce que je cherchais ! Il me faut du temps pour en digérer le contenu mais je pense que GBZM fait partie de ceux qui ont compris comment je fonctionne. -
Dans la page idoine d’itertools, je lis ceci (les parenthèses sont de moi) :
product('ABCD', repeat=2) AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD (avec ordre et répétition) permutations('ABCD', 2) AB AC AD BA BC BD CA CB CD DA DB DC (avec ordre sans répétition) Ccombinations('ABCD', 2) AB AC AD BC BD CD (sans ordre ni répétition) combinations_with_replacement('ABCD', 2) AA AB AC AD BB BC BD CC CD DD (sans ordre avec répétition)Algebraic symbols are used when you do not know what you are talking about.
-- Schnoebelen, Philippe -
Donc au sujet des permutations avec répétition : je reprends l'exemple de la Wikiversité avec les anagrammes du mot "CELLULE" et je vais appliquer ce que GBZM a dit.
Je me donne un ensemble fini, $M$ comme "mot" : $M = \{C,E_1,L_1,L_2,U,L_3,E_2\}$ où je mets des indices pour "a priori" différencier les lettres. $M$ est donc de cardinal $7$. Maintenant, je me donne une partition $\mathcal{P}$ de $M$ : $\mathcal{P} = \{C\} \sqcup \{E_1,E_2\} \sqcup \{L_1,L_2,L_3\} \sqcup \{U\}$, et je prends la relation d'équivalence $\sim$ associée à $P$ : $x \sim y \Longleftrightarrow \forall P \in \mathcal{P}, (x \in P \Longleftrightarrow y \in P)$. Du coup, dans $M/ \mathcal{P}$, on aura bien identifié les lettres entre elles.
Je note $\mathcal{B} = \text{Bij}(\{1,...,7\},M)$ l'ensemble des bijections de $\{1,...,7\}$ dans $M$. J'ai besoin de définir une relation d'équivalence $\equiv$ sur $\mathcal{B}$. Ce qu'il me faut, c'est : $f \equiv g \Longleftrightarrow \forall k \in \{1,...,7\}, f(k) \sim g(k)$. L'ensemble des permutations avec répétitions de $M$ est donc $\mathcal{B}/ \equiv$.
Reste à le dénombrer. Supposons qu'on sait que $|\mathcal{B}| = 7!$. Il faut dénombrer le nombre de classes d'équivalence de $\equiv$. Je comprends que c'est ça qui va faire apparaître le coefficient multinômial, je sais ce qu'il faut montrer, mais je bloque encore un peu sur le "comment". -
$\newcommand\S[1]{\mathfrak{S}_{\{#1\}}}$
Comme le suggère la formule, l'intersection des stabilisateurs des classes d'équivalences est un produit de groupes symétriques : $\S{C}\times\S{E_1,E_2}\times\S{L_1,L_2,L_3}\times\S{U}$. -
Je tombe souvent face à des problèmes que j'arrive presque à résoudre tout seul. Là encore, en lisant ton message, je me dis "pourquoi je n'y ai pas pensé tout seul ?". Parce que c'est tout bête !
En tout cas, oui, c'est logique que je cherche les bijections qui laissent stables les classes de $\mathcal{P}$. D'où l'intersection des stabilisateurs, et ce que tu viens d'écrire devient évident. Merci !
Je m'attaquerai au reste de ce qui a été dit pendant mon absense bientôt :-). Enfin, j'espère, du moins.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 12
+9 Invités