9 – Analyse Combinatoire

cours pdf
A finir : Tauziède

I- Ensembles finis et cardinal d’un ensemble fini.

1°) Produit cartésien d’ensembles finis.

Définition : Soit \(E\) et \(F\) deux ensembles finis et non vides. On appelle produit cartésien de \(E\) par \(F\), noté \(E \times F\), l’ensemble des couples \(\left( {x;y} \right)\) formés d’un élément \(x \in E\) suivi d’un élément \(y \in F\).
Ainsi, \(E \times F = \left\{ {\left( {x;y} \right);x \in E,y \in F} \right\}\).

Exemples :
\(E = \left\{ {a;b;c;} \right\}\) et \(F = \left\{ {1;2} \right\}\). On a :
\(E \times F = \left\{ {\left( {a;1} \right),\left( {a;2} \right),\left( {b,1} \right);\left( {b,2} \right);\left( {c,1} \right);\left( {c,2} \right)} \right\}\) et \(F \times E = \left\{ {\left( {1;a} \right),\left( {1;b} \right),\left( {1,c} \right);\left( {2,a} \right);\left( {2,b} \right);\left( {2,c} \right)} \right\}\).

Remarques :

  • Dans un couple l’ordre est important ; lorsque \(x \ne y\) alors \(\left( {x;y} \right) \ne \left( {y;x} \right)\) (alors que les ensembles \(\left\{ {x;y} \right\}\) et \(\left\{ {y;x} \right\}\) sont égaux). On a donc en général, \(E \times F \ne F \times E\).
  • Si \(E = \emptyset \) ou si \(F = \emptyset \), comme l’ensemble vide ne contient aucun élément, on a alors \(E \times F = \emptyset \).
  • Si \(E\) est un ensemble fini et que \(F = E\), le produit cartésien \(E \times F = E \times E\) est noté \({E^2}\). Cet ensemble est celui des couples \(\left( {x;y} \right)\) où \(x \in E\) suivi d’un élément \(y \in E\).
  • On comprend donc que le produit cartésien « \(x\) » n’a rien à voir avec la multiplication, et que la notation \({E^2}\) n’a rien à voir avec la puissance.

De façon plus générale, pour tout entier naturel \(n\) non nul, on note \({E^n}\) l’ensemble dont les éléments sont des suites ordonnées de \(n\) éléments de \(E\). Ces éléments s’appellent des \(n\)-uplets ou listes de \(n\) éléments.
On convient que lorsque \(n = 1\), \({E^1} = E\).

2°) Injections et surjections de \(\underline {\left[ {{\bf{1\;;p}}} \right]} \) dans \(\underline {\left[ {{\bf{1\;;q}}} \right]} \).

3°) Cardinal d’un ensemble fini.

 

II- Listes d’éléments d’un ensemble fini.

1°) Notion de listes ou de \(\underline {\bf{p}} \)-uplets et arrangements.

Intuitivement, une liste est une énumération qui suit un ordre.

Exemples :

  • La liste d’appel dans l’ordre alphabétique des élèves d’une classe ;
  • La liste des mots du dictionnaire.
  • Les résultats dans l’ordre d’apparition des faces d’une pièce lors de plusieurs lancers successifs.

Définition 1 :
Soit \(E\) un ensemble fini de cardinal \(n\) avec \(n \in \mathbb{N}\)  et \(p \in {\mathbb{N}^*}\). On appelle liste de \(p\)-éléments de \(E\), ou \(p\)-uplet de \(E\), une suite ordonnée de \(p\) éléments \(E\) non nécessairement distincts.

Exemple 1 : Si \(E = \left\{ {a;b;c;d} \right\}\), les triplets \(\left( {a;b;b} \right)\), \(\left( {a;b;d} \right)\), \(\left( {a;d;b} \right)\), \(\left( {a;a;a} \right)\) sont des exemples de triplets que l’on peut former avec trois éléments de \(E\) non nécessairement distincts.

Remarques :

  • La définition donnée est celle d’arrangement avec répétition. Le modèle est celui du tirage avec remise et en tenant compte de l’ordre.
  • Si l’on impose à une liste de \(p\) éléments de \(E\) de ne contenir que des éléments de \(E\) deux à deux distincts, la liste aura moins de \(n\) éléments ce qui signifie que \(1 \le p \le n\). On parle alors d’arrangements sans répétition. Le modèle est celui du tirage sans remise et en tenant compte de l’ordre.

Théorème :

Soit \(E\) un ensemble fini de cardinal \(n\) avec \(n \in {\mathbb{N}^*}\).

  1. Pour tout entier naturel \(p\) non nul, le nombre d’arrangements avec répétition de \(p\) éléments pris parmi les \(n\) éléments de \(E\) (ou de listes à \(p\) éléments de \(E\)) est \({n^p}\).
  2. Pour tout entier naturel \(p\) non nul tel que \(1 \le p \le n\), le nombre d’arrangements sans répétition de \(p\) éléments pris parmi les \(n\) éléments de \(E\) (ou de listes à \(p\) éléments de \(E\) deux à deux distincts) est \(n \times \left( {n – 1} \right) \times \left( {n – 2} \right) \times \cdots  \times \left( {n – p + 1} \right)\).

Preuve : Celle-ci, résulte du principe multiplicatif.
Soit \(E\) un ensemble fini de cardinal \(n\) avec \(n \in {\mathbb{N}^*}\) et \(p\) un entier naturel non nul

  1. Il y’a \(n\) choix possible pour le premier élément du \(p\)-uplet. Comme les éléments du \(p\)-uplet ne sont pas nécessairement distincts, il y’a à nouveau \(n\) choix possibles pour le deuxième élément et ainsi de suite. Il y’a donc pour chacun des \(p\) éléments du \(p\)-uplet \(n\) choix possibles, ce qui donne \(\underbrace {n \times n \times  \cdots  \times n}_{p\;{\rm{ fois}}} = {n^p}\).
  2. Si \(1 \le p \le n\), les éléments étant deux à deux distincts, il y’a n choix possibles pour le premier élément. Cet élément ayant été choisi, il reste \(n – 1\) éléments distincts du premier pour occuper la seconde place du \(p\)-uplet d’où \(n – 1\) choix possibles.

Il reste alors \(n – \left( {p – 1} \right)\) choix possibles pour choisir le \(p\)ème élément du \(p\)-uplet, ce qui donne \(\underbrace n_{\scriptstyle{\rm{premier}}\atop\scriptstyle{\rm{élément}}} \times \underbrace {\left( {n – 1} \right)}_{\scriptstyle{\rm{deuxième}}\atop\scriptstyle{\rm{élément}}} \times \underbrace {\left( {n – 2} \right)}_{\scriptstyle{\rm{troisième}}\atop\scriptstyle{\rm{élément}}} \times  \cdots  \times \underbrace {\left( {n – p + 1} \right)}_{{p^{{\rm{ème}}}}{\rm{ élément}}} = n \times \left( {n – 1} \right) \times \left( {n – 2} \right) \times  \cdots  \times \left( {n – p + 1} \right)\).

Remarque : Le nombre d’arrangements sans répétition de \(p\) éléments pris parmi \(n\) élément, avec \(1 \le p \le n\) se note \(A_n^p\). Ainsi, \(A_n^p = n \times \left( {n – 1} \right) \times \left( {n – 2} \right) \times  \cdots  \times \left( {n – p + 1} \right)\).

Exemple 2 : Une urne contient \(10\) boules indiscernables au toucher numérotées de \(1\) à \(10\). Combien y’a-t-il de tirages possibles de \(3\) boules :

  1. Avec remise (la boule tirée est replacée dans l’urne avant chaque nouveau tirage) ?
  2. Sans remise ?

 

  1. Un tirage de trois boules de l’urne avec remise, est une liste de trois éléments ou un triplet de trois éléments choisis parmi \(10\) éléments, ce qui donne \({10^3} = 1000\) tirages possibles avec remise.
  2. Un tirage de trois boules de l’urne sans remise, est une liste de trois éléments deux à deux distincts ou un triplet de trois éléments deux à deux distincts choisis parmi \(10\) éléments, ce qui donne \(10 \times 9 \times 8 = 720\) tirages possibles sans remise.

Exemple 3 : Combien y a-t-il de façons de ranger cinq paires de chaussettes dans trois tiroirs ?
Comme rien n’est précisé, il peut y avoir plusieurs paires de chaussettes dans le même tiroir. Il s’agit donc de dénombrer le nombre de \(5\)-uplets que l’on peut former avec un ensemble à trois éléments.
Pour la première paire, il y’a trois tiroirs possibles, puis, pour la seconde paire à nouveau trois choix possibles, etc et enfin pour la cinquième paire, trois choix possibles ce qui donne \(3 \times 3 \times 3 \times 3 \times 3 = {3^5} = 243\) façons de ranger cinq paires de chaussettes dans trois tiroirs.

Corollaire : Pour tout entier naturel \(n\) non nul et tout entier naturel \(p\) tel que \(1 \le p \le n\), \(A_n^p = \frac{{n{\rm{ }}!}}{{\left( {n – p} \right){\rm{ !}}}}\).

Démonstration :
Soit \(n\) un entier naturel non nul et \(p\) un entier naturel tel que \(1 \le p \le n\). D’après le théorème précédent, on a : \(A_n^p = n \times \left( {n – 1} \right) \times \left( {n – 2} \right) \times  \cdots  \times \left( {n – p + 1} \right)\) c’est-à-dire encore, \(A_n^p = n \times \left( {n – 1} \right) \times \left( {n – 2} \right) \times  \cdots  \times \left( {n – \left( {p – 1} \right)} \right)\). En multipliant numérateur et dénominateur par \(\left( {n – p} \right) \times \left( {n – \left( {p + 1} \right)} \right) \times \left( {n – \left( {p + 2} \right)} \right) \times  \cdots  \times 2 \times 1 = \left( {n – p} \right){\rm{ }}!\) on a :

\(\begin{array}{l}A_n^p = \frac{{n \times \left( {n – 1} \right) \times \left( {n – 2} \right) \times  \cdots  \times \left( {n – \left( {p – 1} \right)} \right) \times \left( {n – p} \right) \times \left( {n – \left( {p + 1} \right)} \right) \times \left( {n – \left( {p + 2} \right)} \right) \times  \cdots  \times 2 \times 1}}{{\left( {n – p} \right) \times \left( {n – \left( {p + 1} \right)} \right) \times \left( {n – \left( {p + 2} \right)} \right) \times  \cdots  \times 2 \times 1}}\\A_n^p = \frac{{n{\rm{ }}!}}{{\left( {n – p} \right){\rm{ !}}}}\end{array}\).

2°) Permutations.

a-  Permutations sans répétitions d’éléments distincts.

Définition :

Soit \(E\) un ensemble fini de cardinal \(n\) avec \(n \in {\mathbb{N}^*}\).
On appelle permutations de \(E\), toute liste de n éléments de \(E\) deux à deux distincts ou encore, tout \(n\)-uplet de \(E\) formés d’éléments de \(E\) deux à deux distincts.

Exemple 4 :

  • Si \(E = \left\{ {a;b} \right\}\), les permutations de \(E\) sont les couples : \({\sigma _1} = \left( {a;b} \right)\) et \({\sigma _2} = \left( {b;a} \right)\).
  • Si \(E = \left\{ {a;b;c} \right\}\), les permutations de \(E\) sont les triplets :

\({\sigma _1} = \left( {a;b;c} \right)\), \({\sigma _2} = \left( {b;c;a} \right)\), \({\sigma _3} = \left( {c;a;b} \right)\), \({\sigma _4} = \left( {a;c;b} \right)\), \({\sigma _5} = \left( {c;b;a} \right)\) et \({\sigma _6} = \left( {b;a;c} \right)\)

Théorème : Le nombre de permutations d’un ensemble fini à \(n\) éléments, avec \(n \in {\mathbb{N}^*}\), est \(n!\).

Preuve : Une démonstration propre se ferait par récurrence sur \(n\).
Soit \(E\) un ensemble fini de cardinal \(n\) avec \(n \in {\mathbb{N}^*}\). Compter le nombre de permutations d’un ensemble à \(n\) éléments, revient à dénombrer les \(n\)-uplets que l’on peut former avec les \(n\) éléments de \(E\) deux à deux distincts.
Il y’a \(n\) choix possibles pour le premier éléments du \(n\)-uplet, celui étant choisi, il reste \(n – 1\) choix possibles pour le deuxième élément et ainsi de suite ; il reste alors un élément dans \(E\) pour occuper la \(n\)ème place, ce qui donne \(n \times \left( {n – 1} \right) \times \left( {n – 2} \right) \times  \cdots  \times 2 \times 1 = n{\rm{ }}!\) permutations.

Remarque : Cela signifie qu’il y’a \(n{\rm{ }}!\) façons de ranger \(n\) éléments distincts dans tous les ordres possibles.

Exemple 5 : (Le classique : celui des anagrammes d’un mot sans lettre répétée)
Quelles sont les anagrammes du mot \({\rm{PARIS}}\).
Considérons l’ensemble \(E\) formé des cinq lettres (distinctes) du mot \({\rm{PARIS}}\) ; ainsi \(E = \left\{ {{\rm{P}};{\rm{A}};{\rm{R}};{\rm{I;S}}} \right\}\). Compter les anagrammes de ce mot, revient à dénombrer le nombre de permutations de l’ensemble \(E\), c’est-à-dire, revient à compter le nombre de \(5\)-uplets que l’on peut former avec les cinq éléments distincts de l’ensemble \(E\). Ce nombre de permutations est \(5{\rm{ }}! = 120\) ce qui donne \(120\)  anagrammes du mot \({\rm{PARIS}}\).

Attention, on ne procèderait pas de même pour les anagrammes du mot \({\rm{MISSISSIPPI}}\) suivant que l’on distingue ou non les lettres qui se répètent.

b-  Permutations avec répétitions d’éléments discernables. (Mal fait, à refaire).

Il arrive que, parmi les \(n\) objets dont on cherche le nombre de permutations, certains d’entre eux, au nombre de \(k\) (avec \(n \ge k\)) soient tous semblables. Auquel cas, rien ne distingue les permutations de ces \(k\) objets entre eux.

Définition :
Soit \(E\) un ensemble fini de cardinal \(n\) avec \(n \in \mathbb{N}\)  tel que \(n \ge 2\) . Soit \(p\) un entier naturel avec \(p \ge 2\) et considérons \(p\) entiers naturels non nuls \({k_1},{k_2}, \cdots ,{k_p}\) tels que \({k_1} + {k_2} +  \cdots  + {k_p} = n\).
Une permutation avec répétitions de \(n\) éléments de \(E\) est un \(n\)-uplet où figure \({k_1}\) fois un élément de \(E\), \({k_2}\) fois un autre élément de \(E\) (distinct du premier), …, \({k_p}\) fois un autre élément de \(E\) (distinct des \(p – 1\) autres éléments).

Exemple :
Considérons le mot « \({\rm{été}}\) ». Ce mot de trois lettres est constitué de deux lettres distinctes « \({\rm{é}}\) » et « \({\rm{t}}\) » dont deux « \({\rm{é}}\) » se répètent.
Les permutations avec répétition de ce mot sont \(\left( {{\rm{é;t}};{\rm{é}}} \right)\), \(\left( {{\rm{t;é;é}}} \right)\), \(\left( {{\rm{é;é;t}}} \right)\), \(\left( {{\rm{é;é;t}}} \right)\), \(\left( {{\rm{é;t;é}}} \right)\), \(\left( {{\rm{t;é;é}}} \right)\). Or, on remarque que certains triplets sont « identiques ».

Théorème :
Le nombre de permutations avec répétitions de \(n\) éléments d’un ensemble \(E\) de cardinal \(n \ge 2\) pris parmi \(E = \left\{ {{e_1},{e_2}, \cdots ,{e_p}} \right\}\) où figurent \({k_1}\) fois \({e_1}\) , \({k_2}\) fois \({e_2}\), …, \({k_p}\) fois \({e_p}\), avec \({k_1} + {k_2} +  \cdots  + {k_p} = n\) est \(\frac{{n{\rm{ }}!}}{{{k_1}{\rm{ }}!{\rm{ }}{k_2}{\rm{ }}! \cdots {k_p}{\rm{ !}}}}\).

Exemple : Le nombre d’anagrammes du mot « \({\rm{été}}\) » est \(\frac{{3!}}{{1!{\rm{ }}2!}} = 3\).
Le nombre d’anagrammes du mot \({\rm{MISSISSIPPI}}\) est \(\frac{{11!}}{{\underbrace {1!}_{\rm{M}}{\rm{ }}\underbrace {4!}_{\rm{I}}{\rm{ }}\underbrace {4!}_{\rm{S}}{\rm{ }}\underbrace 2_{\rm{P}}!}} = 3\)

3°) Arrangements.

Définition :
Soit \(E\) un ensemble fini de cardinal \(n\) avec \(n \in {\mathbb{N}^*}\) et \(1 \le p \le n\). On appelle arrangement de \(E\), toute liste à \(p\) éléments de \(E\) deux à deux distincts (ou tout \(p\)-uplet constitué d’éléments de \(E\) distincts deux à deux).

Oui, cela a déjà été défini c’est le II, la remarque du 1°).