Chapitre 1

Analyse Combinatoire

1.1 Introduction
L’analyse combinatoire est une branche des mathématiques qui étudie les différentes façons
de sélectionner, organiser et compter des objets ou des éléments dans des ensembles finis. Elle
se concentre sur l’étude des arrangements, des permutations et des combinaisons, ainsi que sur
d’autres concepts liés à la structure et à la manipulation des ensembles discrets.
Les domaines d’applications de cette discipline des mathématiques sont nombreux parmi eux :

1.1.1 Probabilités et statistiques :

L’analyse combinatoire est largement utilisée pour calculer des probabilités dans divers
scénarios, tels que les lancers de dés, les tirages aléatoires et les jeux de cartes. Elle est également
utilisée pour déterminer le nombre de combinaisons possibles dans des échantillonnages et des
expériences aléatoires.

1.1.2 Informatique et algorithmes :

L’analyse combinatoire est essentielle pour concevoir des algorithmes efficaces dans de nom-
breux domaines de l’informatique, tels que la théorie des graphes, la cryptographie, la compres-
sion de données et l’optimisation combinatoire.

1.1.3 Cryptographie :
Dans le domaine de la sécurité de l’information, l’analyse combinatoire est utilisée pour créer
des algorithmes de cryptage et de décryptage robustes, ainsi que pour évaluer la sécurité des
protocoles de communication.

1.1.4 Théorie des graphes :

L’analyse combinatoire est utilisée pour étudier les propriétés et les structures des graphes,
notamment les cycles, les chemins, les arêtes, les sommets et les connexions entre eux. Elle est
également utilisée pour résoudre des problèmes liés aux réseaux, à la planification des itinéraires
et à la logistique.

2
1.1.5 Théorie des nombres :
L’analyse combinatoire est appliquée à de nombreux problèmes de théorie des nombres, tels
que la factorisation des nombres, la recherche de nombres premiers, les congruences et les cycles
de répétition dans les suites numériques.

1.1.6 Optimisation :
Dans les domaines de l’ingénierie, de la logistique et de la planification, l’analyse combinatoire
est utilisée pour résoudre des problèmes d’optimisation, tels que le problème du voyageur de
commerce, l’ordonnancement des tâches et l’affectation des ressources.

1.1.7 Biologie et bioinformatique :

L’analyse combinatoire est utilisée pour modéliser et analyser les interactions entre les gènes,
les protéines et les voies métaboliques. Elle est également utilisée dans la conception de tests
génétiques, la recherche de motifs génétiques et la modélisation des réseaux biologiques.

1.1.8 Jeux et puzzles :

L’analyse combinatoire est utilisée pour étudier et résoudre des problèmes de stratégie dans
les jeux de société, les casse-tête mathématiques et les énigmes logiques.

1.2 Quelques rappels sur la théorie des ensembles

Définition 1.2.1. Selon le célèbre mathématicien Georg Cantor, un ensemble est une collection
d’objets de même nature, définis et distincts. Ces objets étant appelés les éléments de l’ensemble.

Souvent pour distinguer typographiquement un ensemble de ces éléments on utilise une

lettre majuscule pour le désigné (E, F, G, H, ldots), ainsi une lettre minuscule pour designer ces
éléments (x, y, z).
Il existe deux façons pour définir les éléments d’un ensemble :
1. En représentant tous ces éléments (dans le cas où l’ensemble est fini).

Exemple 1.2.1. E={2, -6, 5, 7}

2. Et éventuellement de définir dans le cas où l’ensemble est infini, une relation entre ces
éléments.

Exemple 1.2.2. E = {2n + 1, n ∈ N}.

1.2.1 Appartenance, inclusion, égalité

Appartenance
Si x est un élément d’un ensemble E, on dit aussi que x appartient à E est on écrit x ∈ E.
Si x n’est pas un élément de E, on dit aussi que x n’appartient pas à E est on écrit, x ̸∈ E.

3
Inclusion
On dit qu’un ensemble E est inclus dans un autre ensemble F , si tout élément x de E est
un élément de F . On écrit dans ce cas E ⊂ F .
E ⊂ F ⇐⇒ ∀x ∈ E, x ∈ E =⇒ x ∈ F.
On dit dans ce cas que E est un sous-ensemble de F .

Égalité
Deux ensembles E et F sont égaux s’ils ont les mêmes éléments.
E = F ⇐⇒ (E ⊂ F ∧ E ⊂ F ) ⇐⇒ (x ∈ E ⇐⇒ x ∈ F ).
L’ensemble des nombres réels de racine carrée négative est égale à l’ensemble des nombres réels
x différents de x, et les deux sont égaux à l’ensemble vide, malgré que les raisons d’être vide
sont différentes dans les deux cas.

Réunion, intersection, différence symétrique

a) L’intersection de deux ensembles E et F est l’ensemble notée E ∩ F contenant les éléments
qui sont à la fois dans E et dans F .
E ∩ F = {x, x ∈ E ∧ x ∈ F }.
Si E ∩ F =, on dit alors que les deux ensembles sont disjoints.

b) La réunion de E et F est l’ensemble noté E ∪ F contenant les éléments de E et les éléments

de F comptés une seule fois.
E ∪ F = {x, x ∈ E ∨ x ∈ F }.

b) La différence de l’ensemble E et de l’ensemble F notée E − F est l’ensemble contenant les

éléments de E qui ne sont pas dans F .
E − F = {x, x ∈ E ∧ x ̸∈ F }.

4
Remarque 1.2.1. Si F est un sous-ensemble E, alors E − F est appelé aussi le complémentaire
de F dans E noté CEF .

c) On appelle différence symétrique de E et F l’ensemble noté E∆F et égale à (E − F ) ∪

(F − E).

L’ensemble des parties d’un ensemble

On désigne l’ensemble des parties d’un ensemble E par P(E) qui contient ; l’ensemble vide,
E lui même et tous les sous-ensembles A de E.

P(E) = {∅, E, A/A ⊂ E}.

Exemple 1.2.3. Si E = {x, y, z}, alors P(E) = {∅, E, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}}.

Partition d’un ensemble

On dit qu’une famille finie A1 , A2 , . . . , An de sous-ensembles de E, constitue une partition
pour E si :
i=n
F
1. Ai = A1 ∪ A2 ∪ A3 ∪ . . . ∪ An = E.
i=1
2. ∀ i ̸= j, Ai ∩ Aj = ∅.

Exemple 1.2.4. La famille A1 =] − ∞, 1[, A2 = {1}, A3 =]1, +∞[ est une partition de
l’ensemble des nombres réels.

Produit cartésien
L’ensemble des couples (x, y) tel que x ∈ E et y ∈ F noté E × F est appelé le produit
cartésien de E et F .
E × F = {(x, y)/x ∈ E ∧ y ∈ F }

Exemple 1.2.5. Si E = {1, 2} et F = {a, b} alors

E × F = {(1, a), (1, b), (2, a), (2, b)}.
F × E = {(a, 1), (a, 2), (b, 1), (b, 2)}.

1.2.2 Propriétés
Soient E, F et G 3 ensembles, on admet sans demonstration les relations suivantes :
1. E ∩ F = F ∩ E et E ∪ F = F ∪ E (commutativité de l’intersection et de la réunion).
2. (E ∩ F ) ∩ G = E ∩ (F ∩ G) et (E ∩ F ) ∩ G = E ∩ (F ∩ G) (associativité de l’intersection
et de la réunion).
3. (E ∪ F ) ∩ G = (E ∩ G) ∪ (F ∩ G) et (E ∩ F ) ∪ G = (E ∪ G) ∩ (F ∪ G) (distributivité de
l’intersection (resp de la réunion) sur la réunion (resp sur l’intersection).
4. E − (F ∩ G) = (E − F ) ∪ (E − G) et E − (F ∪ G) = (E − F ) ∩ (E − G).
5. (E ∩ F ) = E ⇐⇒ E ⊂ F et (E ∪ F ) = E ⇐⇒ F ⊂ E.
6. Si F et G sont des sous ensembles de E alors CEF ∩G = CEF ∪ CEG et CEF ∪G = CEF ∩ CEG .

5
2.3 Propriétés des cardinaux
Proposition 2.5. Si E est un ensemble fini non vide et s’il existe une bijection de E sur
F , alors F est fini et Card(E) = Card(F ).
Proposition 2.6. La taille d’une partie est inférieure à la taille du tout : soit B un
ensemble fini,
A ⊂ B implique A est fini; et Card(A) ≤ Card(B)
Attention : la réciproque est fausse !
Proposition 2.7. Deux ensembles finis ayant la même taille et inclus l’un dans l’autre
sont égaux :
(A ⊂ B et Card(A) = Card(B)) implique(A = B)
Remarque 2.8. Cette propriété, très utile, est fausse pour des ensembles infinis.
Par exemple, N∗ ⊂ N, N∗ est en bijection avec N mais N∗ 6= N !!!
Proposition 2.9. Soient E un ensemble fini, A et B deux parties de E.
1. A et B sont disjoints Card(A ∪ B) = Card(A) + Card(B).

2. Card(A B) = card(A) − card(A ∩ B)

3. card(A ∪ B) = card(A) + card(B) − card(A ∩ B)

4. card( A ) = card(E) − card(A)

5. Si (Ai )1≤i≤n est une famille de parties de E deux à deux disjointes alors
n
X
card(A1 ∪ A2 ∪ . . . An ) = card(Ai )
i=1

Proposition 2.10 (Formule du crible (ou de Poincaré)).

1. Cas n = 3 :

card(A1 ∪ A2 ∪ A3 ) = card(A1 ) + card(A2 ) + card(A3 )

− [card(A1 ∩ A2 ) + card(A1 ∩ A3 ) + card(A2 ∩ A3 )]
+ card(A1 ∩ A2 ∩ A3 )

3
 2. Généralisation :
n
X
card(A1 ∪ A2 ∪ · · · ∪ An ) = card(Ai )
i=1
X
− card(Ai1 ∩ Ai2 )
1≤i1 <i2 ≤n
X
+ card(Ai1 ∩ Ai2 ∩ Ai3 )
1≤i1 <i2 <i3 ≤n

+...
X
+ (−1)k+1 card(Ai1 ∩ Ai2 ∩ · · · ∩ Aik )
1≤i1 <i2 <···<ik ≤n

+...
+ (−1)n+1 card(A1 ∩ A2 ∩ · · · ∩ An )

n
X
Proposition 2.11. Si (Ai )1≤i≤n est une partition de E, alors card(E) = card(Ai ).
i=1

3 Dénombrements classiques
3.1 Produit cartésien d’ensembles, p - listes
Proposition 3.1. Soient E1 , E2 , . . . , En n ensembles finis.
Alors le produit E1 × E2 × · · · × En est un ensemble fini, de cardinal :
n
Y
card(E1 × E2 × · · · × En ) = card(E1 ).card(E2 ) . . . card(En ) = card(Ei )
i=1

En particulier, si E est fini, card(E n ) = [card(E)]n .

Exercice : J’ai trois pantalons, cinq chemises et deux paires de chaussures. De

combien de faon puis-je m’habiller ?N = 3 × 5 × 2 = 30
On rappelle qu’une p-liste d’un ensemble à n éléments est un élément de E p (l’ordre
est important et la répétition est possible).

Ainsi, il y a np p-listes d’un ensemble à n éléments.

Dans le modèle de tirages de boules dans une urne, de telles p-listes correspondent aux
tirages successifs et avec remise de p boules dans une urne contenant n boules.
Exercice : J’ai un coffre fort dont le code est composé de 5 chiffres compris entre 0
et 9. Combien existe-t-il de combinaisons différentes ? Un code est un 5- liste; le nombre
de code est N = 105

4
3.2 p-listes d’éléments distincts
Definition 3.2. On appelle arrangement de p éléments de E (ou p-arrangement de E)
toute p-liste d’éléments distincts de E.

Ainsi, l’ordre est important et il n’y a pas de répétition possible.

L’ensemble des p-arrangements de E est souvent noté Ap (E).

Si E est fini de cardinal n, on note Apn le nombre de p-arrangements de E.

Dans le modèle de tirages de boules dans une urne, de tels arrangements correspondent
aux tirages successifs et sans remise de p boules dans une urne contenant n boules.
Exercice: J’assiste à un tiercé (donc 3 chevaux à l’arrivée) et 20 sont au départ. Combien
existe-t-il de tiercés dans l’ordre ? le nombre de tiercés est N = A320
Proposition 3.3. Soit E fini de cardinal n.
n!
1. Alors pour p ≤ n, il existe Apn = = n(n − 1) . . . (n − p + 1) arrangements
(n − p)!
de p éléments de E.
2. Si p > n, il n’existe aucun p-arrangement de E. On pourra noter Apn = 0.
Exemple : A320 = 20 × 19 × 18
Definition 3.4. Un arrangement de n éléments d’un ensemble E à n éléments est appelé
une permutation de E.
Remarque : Lorsque E est composé de lettres, on parle aussi d’anagramme.
Proposition 3.5. Il existe n! permutations d’un ensemble à n éléments.
Il existe n! anagrammes d’un mot composé de n lettres distinctes.
Exercice : Trouver le nombre d’anagrammes du mot CHEV AL. Idem pour le mot
M OU T ON .

3.3 Nombre de parties d’un ensemble

Theoreme 3.6. Un ensemble à n éléments possède 2n parties :

3.4 Combinaisons
Definition 3.7. Soit E un ensemble à n éléments.
On appelle
combinaison de p éléments de E toute partie de E à p éléments.
On note np ( noté aussi Cnp dans certains anciens livres )le nombre de combinaisons de
p éléments de E.

On retiendra que dans une combinaison, l’ordre ne compte pas et il n’y a pas de
répétition possible.

5
 Dans le modèle de tirages de boules dans une urne, une telle combinaison correspond
au tirage simultané de p boules dans une urne contenant n boules distinctes.
Exemple : Combien y-a-t-il de tiercés dans le désordre si 20 chevaux sont au départ ?
Un tiercés dans le désordre
est une combinaison de 3 éléments donc le nombre de tiercés
dans le désordre est N = 203
3
ou C20
n
X
n


Remarque 3.8. On déduit de cette définition et du paragraphe précédent que p
= 2n
p=0
Ce résultat s’obtient aussi en utilisant le binôme de Newton : (1 + 1)n = 2n

n

Apn n!
Proposition 3.9. Pour tout entier n et tout entier p, on a : p
= Cnp = = p!(n−p)!
p!
(cette dernière égalité étant vraie lorsque p ≤ n).
 
n
Proposition 3.10 (Suites strictement croissantes). Il existe exactement suites stricte-
p
ment croissantes de p nombres choisis parmi n.

Démonstration : fabriquer une suite strictement croissante, c’est choisir p éléments

successivement et sans remise parmi les n nombres puis les classer par ordre strictement
croissant.

3.5 Triangle de Pascal - Binôme de Newton

Quelques propriétés des arrangements et des combinaisons