Chapitre 2 Analyse Combinatoire (Le Dénombrement) 2020 [PDF]

Zitiervorschau

Semestre 3

Probabilités et statistiques Analyse combinatoire

Le dénombrement Pr. A. LAHFIDI Pr. A. AAZZAB ENCG AGADIR

1

Plan du chapitre Introduction Définition Champ d’application du dénombrement Le résultat du dénombrement Les principes de base du dénombrement La factorielle I- Méthodes applicables aux situations avec ordre 1- une disposition avec ordre et sans répétition A- Les arrangements sans répétition B- Les permutations sans répétition 2- une disposition avec ordre et avec répétition A- Les arrangements avec répétition B- Les permutations avec répétition II- Méthodes applicables aux situations sans ordre A- Les combinaisons sans répétition B- Les combinaisons avec répétition ENCG AGADIR

2

Introduction

Définition L’analyse combinatoire est une branche des mathématiques qui étudie les «configurations », formées à partir d’« objets » pris dans un ensemble fini donné et disposés en respectant certaines contraintes ou certaines structures fixées. Les deux problèmes principaux sont l’énumération des configurations, et leur dénombrement.

ENCG AGADIR

3

Introduction

Définition Les

dénombrements

(permutations,

arrangements,

combinaisons) jouent un rôle important en probabilités

combinatoires, où l’hypothèse d’équiprobabilité ramène la détermination des probabilités à des comptes d’évènements élémentaires.

ENCG AGADIR

4

Introduction

Champ d’application du dénombrement Les méthodes de comptage développées dans le cadre du dénombrement s’appliquent aux ensembles finis.

ENCG AGADIR

5

Introduction

Le résultat du dénombrement Un groupe d’éléments formé à partir d’éléments d’un ensemble fini est appelé disposition. Deux dispositions se différencient par la nature et par l’ordre des éléments qu’elles contiennent.

Pour la nature : Une disposition est dite sans répétition si aucun des éléments qui lui appartiennent ne peut figurer plus d’une seule fois. E = {a, b, c, d} Une disposition est dite avec répétition si au moins un parmi les éléments qui lui appartiennent apparait plus d’une seule fois. E = {a, a, b, c, c, c, d, d} ENCG AGADIR

6

Introduction

Le résultat du dénombrement Pour l’ordre : Une disposition est dite ordonnée si le changement de l’emplacement d’un élément dans la disposition change la nature de celle-ci. Les parenthèses (…) sont utilisées dans la notation d’un couple. La disposition (x, y) est différente de la disposition (y,x). Une disposition est dite non-ordonnée si l’ordre des éléments qui leur appartiennent n’a pas d’importance. Les accolades ... sont employées dans ce cas. Les dispositions x, y et y,x sont équivalentes ENCG AGADIR

7

Introduction

Les principes de base du dénombrement Deux principes fondamentaux : la multiplication et l’addition La multiplication est utilisée lorsque le problème traité consiste à choisir des éléments à partir d’un ensemble et que chaque choix dépend de celui qui le précède. C’est le cas où on fait un choix et on fait un autre. Exemple 1 : élire 3 membres parmi 20 employés d’une entreprise pour siéger dans un comité. Exemple 2 : créer des codes de 4 chiffres avec répétition et sans répétition. ENCG AGADIR

8

Introduction

Les principes de base du dénombrement Deux principes fondamentaux : la multiplication et l’addition L’addition est utilisée lorsque le problème traité consiste à choisir des éléments à partir d’un ensemble et que chaque choix est indépendant de celui qui le précède. C’est le cas où on fait un choix ou bien un autre. Exemple : former un comité composé d’au plus de 3 membres choisis parmi 20 employés.

ENCG AGADIR

9

Introduction

La principale opération mathématique utilisée dans le dénombrement La factorielle est l’opération mathématique la plus employée dans les formules du dénombrement. C’est une application de ℕ dans ℕ notée par un point d’exclamation qui suit un entier naturel n : n! et qui se lit factorielle n.

n!= n × (n -1) × (n - 2) × (n - 3) × (n - 4)…× 3× 2 ×1 Par convention : 0! = 1

ENCG AGADIR

10

Introduction

La principale opération mathématique utilisée dans le dénombrement Remarque: il est possible de simplifier un rapport composé de factorielles. Pour faire cette simplification, il est très utile d’employer la formule de multiplication d’un entier naturel par une factorielle. Exemples:

6! 6  5  4!   6  5  30 4! 4! 10! 10  9  8  7   840 6!3! 3  2 1 ENCG AGADIR

11

Les méthodes du dénombrement Pour savoir la méthode à appliquer dans le cadre du dénombrement, il est nécessaire d’avoir au préalable les informations suivantes :  Le nombre n d’éléments de l’ensemble à partir duquel le choix sera effectué (le cardinal de l’ensemble) ;  Le nombre p d’éléments à choisir à partir de l’ensemble ;  La modification de l’ordre des éléments modifie-t-elle la disposition (disposition ordonnée) ou n’y exerce aucune influence (disposition non ordonnée) ;  Un élément peut apparaitre plus d’une seule fois dans la disposition (avec répétition) ou doit-il y figurer une seule fois (sans répétition). ENCG AGADIR

12

Les méthodes du dénombrement I- Méthodes applicables aux situations avec ordre

Les situations avec ordre sont représentées par des dispositions qui changent si l’emplacement d’un élément qui leur appartient se modifie. Dans ce cas nous avons deux cas de figure : 1- une disposition avec ordre et sans répétition ou 2- une disposition avec ordre et avec répétition.

ENCG AGADIR

13

Les méthodes du dénombrement

I- Méthodes applicables aux situations avec ordre 1- une disposition avec ordre et sans répétition A- Les arrangements Lorsqu’on choisit p parmi n éléments tel que p  n ,que la répétition des éléments n’est pas tolérée (éléments discernables) et que l’ordre de ces éléments doit être respecté (disposition ordonnée), alors la disposition est appelée : arrangement. p A Celle-ci est notée n et se lit : arrangement de p éléments choisis parmi n. Avec :

n! A  = n × (n - 1) × (n - 2) ×…× (n - p + 1) (n - p)! p n

ENCG AGADIR

14

Les méthodes du dénombrement

I- Méthodes applicables aux situations avec ordre 1- une disposition avec ordre et sans répétition A- Les arrangements Exemples : 1. Combien pouvons-nous former de dispositions ordonnées sans répétition de deux lettres choisies parmi les lettres A, B et C ? 2. Quel est le nombre de comités de 3 membres qu’on peut former de 10 individus ? 3. A chaque voyage, un représentant de commerce visite 6 des 9 villes de sa région. De combien de manières peut-il organiser son itinéraire ? ENCG AGADIR

15

Les méthodes du dénombrement

I- Méthodes applicables aux situations avec ordre 1- une disposition avec ordre et sans répétition A- Les arrangements Exemples : 4. Combien de tiercés gagnants dans l’ordre peut-on imaginer avec 14 chevaux au départ ? 5. Combien y a t-il de nombres de 4 chiffres différents ne commençant pas par 0 ?

ENCG AGADIR

16

Les méthodes du dénombrement

I- Méthodes applicables aux situations avec ordre 1- une disposition avec ordre et sans répétition B- Les permutations Une permutation notée P est un arrangement où p=n. Le nombre de permutations sans répétition de n éléments est exprimé par :

n! PA  = n! n × (n - 1) ×…× 2 1 (n - n)! n n

Exemple 1 : Combien de façons a-t-on pour composer le mot de passe d’un fichier électronique de 6 chiffres? Exemple 2 : Combien de façons a-t-on pour composer le mot de passe d’un fichier électronique de 6 chiffres différents? ENCG AGADIR

17

Les méthodes du dénombrement

I- Méthodes applicables aux situations avec ordre 2- une disposition avec ordre et avec répétition A- Les arrangements avec répétition (𝒜np en italique) L’arrangement avec répétition de p éléments choisis parmi n est une disposition ordonnée où un élément peut figurer plus d’une seule fois. Le nombre de ces arrangements se calcule selon la formule suivante : p p

× n × n × … × n=n 𝒜n n   p fois

Exemple : on réalise trois tirages successifs avec remise d’une boule parmi 10 numérotés de 1 à 10. Combien peut-on avoir de possibilités ? ENCG AGADIR 18

Les méthodes du dénombrement

I- Méthodes applicables aux situations avec ordre 2- une disposition avec ordre et avec répétition B- Les permutations avec répétition Si les n éléments se composent de sous-ensembles n1,n2,n3,…,nk discernables et que n= n1+n2+n3+…+nk, alors le nombre de permutations avec répétition est de

n! P= n1!×n2!×n3!×…× n k ! Exemple : Combien de mots peut-on former avec 2 R, 3 V et 4 B? ENCG AGADIR

19

Travail à faire 1. Combien d’anagrammes peut-on obtenir par le mot « MAISON » ?

2. Combien d'anagrammes peut-on former avec les lettres du mot « EXCELLENCE » ? 3. Après les prolongations d'un match de football, l'entraîneur doit choisir les 5 tireurs de penaltys parmi les onze joueurs et l'ordre de passage. Combien de choix a-t-il ? 4. Combien de numéros de téléphone composés de 7 chiffres existe-til ? ENCG AGADIR

20

Les méthodes du dénombrement II- Méthodes applicables aux situations sans ordre

Une disposition qui ne subit pas de modifications lorsque l’ordre des éléments qui lui appartiennent change est dite sans ordre. 1- Si elle ne tolère pas la répétition d’un de ses éléments, elle est dite sans répétition

2- En revanche, elle est dite avec répétition dans le cas où au moins un de ses éléments peut apparaitre plus d’une seule fois. ENCG AGADIR

21

Les méthodes du dénombrement

II- Méthodes applicables aux situations sans ordre 1- une disposition sans ordre et sans répétition A- Les combinaisons sans répétition La combinaison sans répétition de p éléments choisis parmi n (p  n) est la disposition où le changement de l’ordre des p éléments n’a aucune influence sur la disposition et où aucun élément ne peut y apparaitre plus d’une seule fois. La formule de calcul : p A n! Cnp   n p!(n - p)! p! ENCG AGADIR

22

Les méthodes du dénombrement

II- Méthodes applicables aux situations sans ordre 1- une disposition sans ordre et sans répétition A- Les combinaisons sans répétition Exemple 1 : Déterminez le nombre d’équipes de 3 travailleurs qu’on peut former de 10 travailleurs. Exemple 2 : Cinq tennismen et quatre tenniswomen participent à un tournoi. Déterminer le nombre de matches distincts que l’on peut organiser a) en simples messieurs b) en simples dames c) en doubles messieurs d) en doubles dames e) en doubles mixtes ENCG AGADIR 23

Les méthodes du dénombrement

II- Méthodes applicables aux situations sans ordre 1- une disposition sans ordre et sans répétition A- Les combinaisons sans répétition Exemple 3 : Nous voulons former une équipe de 4 personnes à partir de 12 garçons et 8 filles. Quel est le nombre de possibilité pour former : a) Une équipe b) Une équipe des garçons c) Une équipe des filles d) Une équipe du même sexe e) Une équipe d’au moins un garçon

ENCG AGADIR

24

Les méthodes du dénombrement

II- Méthodes applicables aux situations sans ordre 1- une disposition sans ordre et sans répétition A- Les combinaisons sans répétition Propriétés des combinaisons sans répétitions

.

Cn0  Cnn  1 ; où n  0. Cnp  Cnn  p ; où 0  p  n. C C 1 n

n 1 n

 n ; où n  0.

n p 1 C  Cn 1 ; où 1  p  n  1 et n  0. p p n

ENCG AGADIR

25

Les méthodes du dénombrement

II- Méthodes applicables aux situations sans ordre 1- une disposition sans ordre et sans répétition A- Les combinaisons sans répétition La formule du binôme de Newton

(a + b) = p0 Cpn  a p  b n p n

n

où (a,b)∈ R² et n ∈ N Exemple: Développer à l’aide de la formule du binôme de Newton les expressions suivantes : (a+b)² et (a+b)4

La formule du triangle de Pascal

C C p n

p n -1

C

ENCG AGADIR

p-1 n -1

où 1  p  n  1. 26

Les méthodes du dénombrement

II- Méthodes applicables aux situations sans ordre 1- une disposition sans ordre et sans répétition B- Les combinaisons avec répétition Une combinaison avec répétition de p éléments choisis parmi n est une disposition non ordonnée où un élément peut apparaitre plus d’une seule fois. La formule de calcul :

K

p n

C

p n  p -1



n  p - 1 ! p!n  1 !

Exemple : Quel est le nombre de combinaisons possibles, avec répétition de 2 lettres choisies parmi a, b, c et d ? ENCG AGADIR

27

Résumé

Tirage de p éléments parmi n

Tirage Avec remise Sans remise

Avec ordre

n

p

p n

A

ENCG AGADIR

Sans ordre

C

p n  p 1

C

p n

28

Exercices

Exercice 1:

1. Déterminez le nombre de sous-ensemble E={1,2,3,4,5,6} 2. Combien de sous-ensembles de E contiennent le chiffre 2 ? 3. Quel est le nombre de sous-ensembles de E qui incluent exactement 3 chiffres ? 4. Combien de mots de passe de 9 lettres peut-on d’obtenir du mot :

SECURISER ?

ENCG AGADIR

29

Exercices

Exercice 2: 1- Calculez les valeurs numériques suivantes : a. 5! 4!

b. 50!4!47!6!

c.

52!

5!47!

2- Transformez en notations factorielles les expressions suivantes : a. 15 ×16 ×17 ×18 b. 112 ×13 ×14 c. 10 × 9 × 8 4 × 3

3- Simplifiez les expressions suivantes : a.

n  1 !

n  2 !

b.

k!

k  1 !

ENCG AGADIR

c.

p! 3!p - 3!

30

Exercices Exercice 3: A- Une équipe de travail est composée d’un superviseur, de deux responsables opérationnels et de 10 agents d’exécution. L’entreprise emploie 4 ingénieurs en génie mécanique, 8 techniciens en fabrication mécanique et 50 ouvriers d’exécution. Combien d’équipes l’entreprise peut-elle former ? B- Il est estimé que 25 parmi les 500 unités réceptionnées d’un produit sont défectueuses. On choisit 4 unités au hasard afin de les contrôler. Quel est le nombre de cas où on trouve au moins un produit défectueux ? Quel est le nombre de cas possibles ? ENCG AGADIR

31

Exercices Exercice 3: C- Un questionnaire contient 10 questions chacune avec 5 modalités de réponse. Le répondant est sollicité de répondre à toutes les questions en cochant au moins une réponse. Quel est le nombre de réponses possibles ? D- Votre entreprise a décidé de changer le système de codification de ses fichiers clients. Au lieu d’un code composé de 5 chiffres, elle opte pour un code de 2 chiffres et 2 lettres, tous différents. La nouvelle codification offre-t-elle plus de possibilités que l’ancienne ? E- Un fabricant de produits de cosmétique offre une gamme de 4 parfums, une gamme de 5 eaux de toilette, une gamme de 2 gels douche et une gamme de 6 déodorants. Combien d’assortiments contenant un seul produit par gamme sera-t-il en mesure d’offrir ? ENCG AGADIR 32

Exercices Exercices de synthèse 1. Combien de codes de 5 éléments peut-on former dans les cas suivants : a. Les codes se composent des chiffres de 0 à 9 ; b. Les codes se composent des lettres de l’alphabet ; c. Les codes contiennent 3 chiffres de 0 à 9 et deux lettres de l’alphabet.

2. Un questionnaire compte 20 questions, chacune avec 5 modalités de réponse. La personne interrogée est sollicitée de répondre à toutes les questions en cochant une seule réponse. Combien existe-t-il de réponses possibles ?

ENCG AGADIR

33

Exercices Exercices de synthèse 3. Nous voulons former des codes de 4 chiffres dont le premier n’est pas nul. a. Combien de codes peut-on créer ? b. Combien de codes de chiffres différents peut-on créer ? c. Combien peut-on créer de codes composés d’au moins deux chiffres identiques ? d. Combien peut-on créer de codes composés de chiffres différents autres que 6 et 4 ? 4. Chaque personne d’un groupe de 46 individus serre la main d’une personne d’un groupe de 70 individus. En présence d’une bactérie contagieuse dans les mains des individus du premier groupe, quel est le nombre de possibilités qu’elle soit transmise aux membres du deuxième groupe. ENCG AGADIR

34

Exercices Exercices de synthèse 5. De 20 employés composés de 6 femmes (y compris F) et de 14 hommes (y compris M), l’entreprise veut former des groupes de travail de 4 individus. a. Combien de groupes peut-on former ? b. Combien de groupes d’hommes peut-on former ? c. Combien de groupes de 2 femmes et 2 hommes peut-on former ? d. Combien de groupes d’au moins une femme peut-on former ? e. Combien de groupes d’au plus 2 hommes peut-on former ? f. Dans combien de groupes peut figurer F ? g. Dans combien de groupes peut figurer M ? h. Dans combien de groupes peut-on éviter d’associer F et M ?

ENCG AGADIR

35

Exercices Exercices de synthèse 6. Parmi 1000 unités d’un produit, on choisit 20 unités pour les contrôler. La proportion des produits défectueux est estimée à 5%. a. Combien de choix sont possibles ?

b. Combien de choix comportent uniquement des produits défectueux ? c. Combien de choix comportent uniquement des produits non défectueux ? d. Combien de choix comportent au moins un produit

défectueux ? ENCG AGADIR

36

Merci de votre attention

ENCG AGADIR

37