Chapitre 1
Analyse Combinatoire
L’étude de l’analyse combinatoire ou du dénombrement porte sur les différentes
manières de disposer ou de sélectionner les objets d’un ensemble fini.
1.1 Principe fondamental de dénombrement
Si une opération globale peut être décomposée en p opérations élémentaires
successives, et que ces opérations peuvent être effectuées respectivement de n1 ,
n2 , ..., np façons différentes, alors le nombre total de façons d’effectuer ces
opérations est égal au produit :
N = n1 × n2 × · · · × np .
Exemples 1.1.1 :
1. Examen Vrai/Faux : Combien y a-t-il de possibilités différentes pour
répondre au hasard à un examen de 10 questions ayant comme choix vrai
ou faux ? Chaque question ayant 2 choix (vrai ou faux), il y a donc
210 = 1024 façons différentes de répondre.
2. Numéros de téléphone : Déterminer le nombre de numéros de téléphone
marocains qui commencent par 07. Ce numéro se compose de 8 chiffres.
Les 6 autres chiffres peuvent être choisis parmi 10 possibilités (0 à 9), ce
qui donne 106 = 1000000 numéros possibles.
3. Code PIN oublié : Si un étudiant a oublié le code PIN de son téléphone,
qui est composé de quatre chiffres tous distincts, combien d’essais sont
nécessaires pour tenter le code ? Le nombre total de combinaisons de 4
chiffres, tous distincts, parmi 10 est de 10 × 9 × 8 × 7 = 5040 possibilités.
1.2 Arrangements
Définition 1.2.1
Soit E un ensemble de n objets. Un arrangement de p objets est une suite
ordonnée de p objets sélectionnés parmi les n objets de l’ensemble E.
1
Propriétés 1.2.2
1. Arrangements avec répétition : Le nombre d’arrangements avec répétition
de p objets parmi n est donné par :
np
2. Arrangements sans répétition : Le nombre d’arrangements sans répétition
de p objets parmi n (avec n ≥ p) est donné par :
n!
Apn = = n × (n − 1) × · · · × (n − p + 1).
(n − p)!
1.3 Permutations
Définition 1.3.1
Soit E un ensemble de n objets. Une permutation est un arrangement de tous
les objets de E.
On rappelle la convention usuelle : 0! = 1.
Propriétés 1.3.2
1. Permutations sans répétition : Le nombre de permutations de n objets
distincts est donné par n!.
2. Permutations avec répétition : Le nombre de permutations de n objets
dont Il y a n1 objets de type 1 (identiques entre eux), n2 objets de type 2
(identiques entre eux), . . ., np objets de type p (identiques entre eux) est :
n!
n1 ! × n2 ! × · · · × np !
1.4 Combinaisons
Définition 1.4.1
Soit E un ensemble de n objets. Une combinaison de p objets parmi n (avec
n ≥ p) est un sous-ensemble de E composé de p objets choisis sans répétition
parmi les n objets.
Remarque : Pour les arrangements et les combinaisons sans répétition, il
faut que n ≥ p, sinon ces notions n’ont pas de sens. En revanche, dans le cas
avec répétition, cette condition n’est pas nécessaire.
2
Propriétés 1.4.2
1. Le nombre de combinaisons de p objets pris parmi n est donné par :
n!
Cnp = .
p!(n − p)!
2. Symétrie des combinaisons : Cnp = Cnn−p .
p−1 p
3. Relation de Pascal : Cnp = Cn−1 + Cn−1 .
n
4. Formule du binôme de Newton : (a + b)n = Cnk ak bn−k .
P
k=0
n! n1 n2 n
5. Formule du binôme généralisée : (a1 +a2 +· · ·+ap )n =
P
n1 !×n2 !×···×np ! a1 a2 . . . ap p
n1 +n2 +···+np =n
1.5 Cardinal d’un ensemble fini
Définition 1.5.1
Soit E un ensemble fini. Le cardinal de E est le nombre d’éléments de E, noté
card(E) ou |E|.
Théorèmes 1.5.2
1. Si E et F sont deux ensembles finis, alors : card(E ∪ F ) = card(E) +
card(F ) − card(E ∩ F ).
2. Le cardinal de l’ensemble des parties de E est donné par : card(P (E)) =
2card(E) , où P (E) est l’ensemble des parties de E.
Exemple : Si E = {a, b, c}, alors card(E) = 3. L’ensemble des parties de E est
P (E) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.
On vérifie que card(P (E)) = 8 = 23 .