Ch 13 ANALYSE COMBINATOIRE Tspé

« Ch 13 ANALYSE COMBINATOIRE Tspé Sauf mention contraire, les lettres majuscules désignent des ensembles finis. L’ensemble vide, noté ∅, est l’ensemble qui ne possède aucun élément. On pourra utiliser les notations vues en probabilités : A ∪ B, A ∩ B, A. Attention, A ∪ B signifie "A ou B" au sens inclusif, c’est sous-entendu "A ou B ou les deux" La notation A ⊂ B signifie que A est inclus dans B, au sens large (on a toujours A ⊂ A) Avec a et b deux entiers, on note Ja; bK l’ensemble des entiers compris entre a et b. 1 Cardinal d’un ensemble définition (cardinal) : Le cardinal de E, noté |E|, est le nombre d’éléments de E. Remarques : - On rencontre aussi les notations Card E ou #E - Un ensemble à n éléments peut toujours être assimilé à J1; nK propriété immédiate : si A ⊂ B, alors |A| 6 |B| 2 2.1 Principe additif Union disjointe définition : A et B sont disjoints lorsque A ∩ B = ∅ notation : l’union de deux ensembles disjoints A et B se note A ⊔ B définition (partition) : A1 , A2 , ...

, An forment une partition de E lorsque leur union est égale à E et qu’il sont deux à deux disjoints (Ai ∩ Aj = ∅ si i 6= j).

On écrit alors : E = A1 ⊔ A2 ⊔ ...

⊔ An Remarque : Si A ⊂ E, alors A et A constituent une partition de E. 2.2 principe additif propriété (principe additif) : |A1 ⊔ A2 ⊔ ...

⊔ An | = |A1 | + |A2 | + ...

+ |An | 1 Ch 13 2.3 ANALYSE COMBINATOIRE Tspé Cardinal d’une union quelconque propriété : |A ∪ B| = |A| + |B| − |A ∩ B| Conséquence immédiate : pour tous ensembles A et B, |A ∪ B| 6 |A| + |B| Remarque : La généralisation de cette formule existe mais n’est pas simple, c’est la "formule du crible". Preuve : Notons A′ l’ensemble des éléments qui sont dans A mais pas dans B. Notons A′′ l’ensemble des éléments qui sont dans B mais pas dans A. Ainsi, A = A′ ⊔ (A ∩ B) et B = A′′ ⊔ (A ∩ B). ( |A| = |A′ | + |A ∩ B| Donc |B| = |A′′ | + |A ∩ B| Et A ∪ B = A′ ⊔ (A ∩ B) ⊔ A′′ donc |A ∪ B| = |A′ | + |A ∩ B| + |A′′ | = |A| − |A ∩ B| + |A ∩ B| + |B| − |A ∩ B| = |A| + |B| − |A ∩ B| Exercice 1 Un lycée propose deux options : musique et théâtre. Chaque élève peut ne choisir aucune option, ou n’en choisir qu’une, ou choisir les deux. Dans une classe de 32 élèves : 12 élèves ont choisi l’option musique 13 élèves ont choisi l’option théâtre 10 élèves n’ont choisi aucune option Déterminer le nombre d’élèves qui n’ont choisi que musique, qui n’ont choisi que théâtre, qui ont choisi les deux options (on pourra s’aider d’un diagramme ou d’un tableau). Exercice 2 On considère un ensemble E de personnes. 70 personnes ont moins de 30 ans et 50 personnes ont plus de 20 ans. On notera M l’ensemble des moins de 30 ans et P l’ensemble des plus de 20 ans. 1.

Justifier que 70 6 |E| 6 120 2.

Donner un exemple de répartition des âges dans ce groupe pour lequel : a) |E| = 70 b) |E| = 120 2 Ch 13 3 ANALYSE COMBINATOIRE Tspé Produit cartésien 3.1 Cas de deux ensembles définition : On note E × F l’ensemble des couples (x; y) avec x ∈ E et y ∈ F . Remarque : on tient compte de l’ordre.

Par exemple (1; 2) et (2; 1) sont deux couples distincts. propriété (principe multiplicatif) : |E × F | = |E| × |F | Exemple : le nombre de couples (x; y) avec x ∈ J1; 5K et y ∈ J1; 7K est 35 car 5 × 7 = 35 3.2 Cas général définition : On note E1 × E2 × ...

× Ek l’ensemble des listes (x1 ; x2 ; ...; xk ) où xi ∈ Ei ∀i. On dit aussi k-liste ou k-uplet. On note E k l’ensemble E × E × ...

× E | {z } k fois Remarque : on tient compte de l’ordre comme dans le cas précédent. propriété (principe multiplicatif) : |E1 × E2 × ...

× Ek | = |E1 | × |E2 | × ...

× |Ek | en particulier : si |E| = n, alors |E k | = nk Exemple : le nombre de triplets (x; y; z) avec x, y, z ∈ J1; 4K est 64 car 43 = 64 3.3 En terme de choix de k éléments parmi n ( avec ordre nk est le nombre de façons de choisir k éléments parmi n avec répétition Commentaires : - "avec ordre" signifie qu’on tient compte de l’ordre dans lequel sont choisis les éléments. - "avec répétition" signifie qu’on peut choisir plusieurs fois le même élément. Typiquement : tirage successif de k boules dans une urne qui en contient n, avec remise. 3 Ch 13 ANALYSE COMBINATOIRE Tspé Exercice 3 un restaurant propose 5 entrées, 4 plats et 6 desserts.

Combien de menus différents peut-on choisir dans ce restaurant ? Exercice 4 En informatique, on utilise le système binaire pour coder les caractères.

Un bit est un élément qui prend la valeur 0 ou 1.

Un octet est composé de 8 bits.

Combien de caractères un octet peut-il coder ? Exercice 5 On doit ranger 5 pulls de couleurs différentes dans 3 tiroirs.

Chaque tiroir peut contenir autant de pulls qu’on veut (y compris aucun). 1.

Combien y-a-t-il de rangements possibles ? 2.

Combien y-a-t-il de rangements dans lesquels aucun tiroir n’est vide ? Exercice 6 Soit E un ensemble.

Une partie de E est un sous-ensemble de E.

Tout ensemble E possède une seule partie possédant 0 éléments, cette partie est notée ∅.

De plus, E lui-même constitue une de ses parties. Le but de l’exercice est de déterminer le nombre de parties d’un ensemble à n éléments. 1.

Soit E = {a; b} Déterminer toutes les parties de E. 2.

Même question avec E = {a; b; c} 3.

Soit E = J1; 4K On peut représenter une partie quelconque F de E par une 4-liste (x1 ; x2 ; x3 ; x4 ) de J0; 1K4 de la manière suivante : ( i ∈ F si xi = 1 i 6∈ F si xi = 0 a.

Ecrire les parties représentées par (0; 0; 1; 1) , (1; 0; 1; 0), (0; 0; 1; 0), (1; 1; 1; 0). b.

Ecrire les 4-listes de J0; 1K4 représentant les parties {1; 2} , {2; 3; 4} , {4} , ∅. c.

Déterminer le nombre de parties de E. 4.

Soit E un ensemble de cardinal n. En généralisant le raisonnement précédent, déterminer le nombre de parties de E. 4 Ch 13 4 ANALYSE COMBINATOIRE Tspé Arrangements 4.1 Cas général définition : Un arrangement de E est une liste d’éléments de E deux à deux distincts. propriété : Soit E un ensemble de cardinal n, et k ∈ J0; nK. Le nombre d’arrangements à k éléments de E se note Akn Akn = n × (n − 1) × ...

× (n − k + 1) {z } | k facteurs ce qu’on peut aussi écrire Akn = n! (n − k)! Remarque : la formule précédente vaut pour k = 0, et A0n = 1.

Par convention, le fait de ne choisir aucun élément constitue un choix possible. 4.2 Akn En terme de choix de k éléments parmi n ( avec ordre est le nombre de façons de choisir k éléments parmi n sans répétition Typiquement : tirage successif de k boules dans une urne qui en contient n, sans remise. 4.3 Permutations définition : Soit E un ensemble de cardinal n. Une permutation de E est un arrangement à n éléments de E. Concrètement, une permutation est un rangement des éléments de E dans un certain ordre. propriété : Si |E| = n, alors le nombre de permutations de E est n! 5 Ch 13 ANALYSE COMBINATOIRE Tspé Exercice 7 On considère un groupe de 10 personnes, que l’on dispose en file indienne, au hasard. 1.

Combien y-a-t-il de files possibles ? 2.

Parmi ces 10 personnes, il y a Tom, Yann et Léa. a.

Quelle est la probabilité que Tom et Yann soient côte à côte (dans un ordre quelconque) ? b.

Quelle est la probabilité que Tom,Yann et Léa soient côte à côte (dans un ordre quelconque) ? Exercice 8 Huit candidats prennent le départ d’une course.

Le podium sera constitué des trois premiers. On considère qu’il y a équiprobabilité. 1..... »