Chapitre 1 Analyse combinatoire

Chapitre 1 : Analyse Combinatoire Dr. BEHIANI Ridha Email: [email protected] Année universitaire 2025/2026 Introduction La théorie des ensembles forme le socle de nombreux concepts mathématiques. Cette sec- tion a pour objectif d’en rappeler les notions fondamentales : la définition d’un ensemble et de ses éléments, ainsi que les relations et opérations qui les caractérisent. Ces rappels sont essentiels pour aborder sereinement les principes de l’analyse combinatoire, qui fera l’objet de la section suivante. 1 Rappels sur les ensembles 1.1 La notion d’ensemble Définition 1.1. Un ensemble est une collection d’objets. Ces objets sont appelés éléments de l’ensemble. Pour dire que x est un élément de l’ensemble E, on écrit x ∈ E. Pour dire que x n’est pas un élément de E, on écrit x /∈ E. Un ensemble est caractérisé par ses éléments. Deux ensembles A et B sont donc égaux s’ils ont les mêmes éléments. On note alors A = B. Remarque 1.1. On peut définir un ensemble : — En extension : en donnant la liste de ses éléments. Par exemple E =. — En compréhension : en donnant une propriété qui caractérise ses éléments. Par exemple E =. Remarque 1.2. Notation des ensembles de nombres : — N : ensemble des entiers naturels — Z : ensemble des entiers relatifs — Q : ensemble des rationnels — R : ensemble des réels 1.

Chapitre 1 : Analyse Combinatoire — N∗ : entiers naturels non nuls — R∗ : réels non nuls — R+ : réels positifs Exemple 1.1. Les ensembles ne sont pas nécessairement des ensembles de réels. On peut considérer l’ensemble constitué des jours de la semaine : E =. Définition 1.2 (Ensemble vide). Un ensemble particulier est l’ensemble ne contenant aucun élément, on l’appelle l’ensemble vide et on note cet ensemble ∅. Définition 1.3 (Ensembles finis et infinis). Un ensemble E est dit fini lorsque le nombre d’éléments qui le composent est un entier naturel. Dans ce cas, le nombre d’éléments est appelé le cardinal de l’ensemble. On le note card(E). On dit qu’un ensemble est infini s’il comporte un nombre infini d’éléments. Exemple 1.2. L’ensemble E = est fini de cardinal card(E) = 10. L’ensemble N des entiers positifs ou nuls est un ensemble infini. 1.2 Opérations sur les ensembles Définition 1.4 (Réunion). Soient A et B deux ensembles. On appelle réunion de A et B, notée A ∪ B, l’ensemble des éléments qui appartiennent à A ou à B : A ∪ B = Exemple 1.3. Si A = et B =, alors A ∪ B =. L’élément 3 qui se trouve dans A et dans B n’est pas répété dans A ∪ B. Définition 1.5 (Intersection). Soient A et B deux ensembles. On appelle intersection de A et B, notée A ∩ B, l’ensemble des éléments qui appartiennent à la fois à A et à B : A ∩ B = Exemple 1.4. Si A = et B =, alors A ∩ B =. Définition 1.6 (Différence). Soient A et B deux ensembles. On appelle A moins B, et on note A \ B, l’ensemble des éléments de A qui ne sont pas dans B : A \ B = Exemple 1.5. Si A = et B =, on a A \ B = et B \ A =. Remarque 1.3. Pour tout ensemble A, on a A \ ∅ = A, et A \ A = ∅. De plus, pour tous ensembles A et B, on a une équivalence A ⊂ B ⇔ A \ B = ∅. Exemple 1.6. Si A = et B =, alors B \ A =. Dr. BEHIANI Ridha Email: [email protected] Page 2/11.

Chapitre 1 : Analyse Combinatoire Définition 1.7 (Complémentaire). Soit A une partie d’un ensemble E. On appelle complé- mentaire de A dans E le sous-ensemble de E, noté CEA ou A, constitué des éléments de E qui n’appartiennent pas à A : A = Exemple 1.7. Soit E =. Soit A =. On a CEA =. Soit B = CEA. On a CEB = = A. 1.3 Propriétés des opérations ensemblistes Proposition 1.1. Pour tous ensembles A, B et C contenus dans E, on a les propriétés suivantes : — Complémentaire : E = ∅ ∅ = E A = A A ⊂ B ⇒ B ⊂ A — Lois de Morgan : A ∩ B = A ∪ B A ∪ B = A ∩ B — Réunion : A ∪ B = B ∪ A A ∪ (B ∪ C) = (A ∪ B) ∪ C A ∪ A = A A ∪ ∅ = A A ∪ E = E — Intersection : A ∩ B = B ∩ A A ∩ (B ∩ C) = (A ∩ B) ∩ C A ∩ A = A A ∩ ∅ = ∅ A ∩ E = A — Distributivité : A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) Dr. BEHIANI Ridha Email: [email protected] Page 3/11.

Chapitre 1 : Analyse Combinatoire Remarque 1.4. Les ensembles ainsi que les opérations qui leur sont associées peuvent être représentés à l’aide de diagrammes appelés diagrammes de Venn. A B A ∩ B A B A ∪ B 1.4 Ensemble des parties d’un ensemble Définition 1.8 (Ensemble des parties). Soit E un ensemble. L’ensemble de toutes les parties de E est appelé ensemble des parties de E et il est noté P(E). En d’autres termes, A ∈ P(E) signifie que A ⊆ E. Remarque 1.5. Les éléments de P(E) sont des sous-ensembles de E, et non pas des éléments de E. De plus, contrairement à l’ensemble E qui peut être vide, l’ensemble P(E) n’est jamais vide, puisqu’il contient toujours au moins les ensembles ∅ et E. Exemple 1.8. Si E =, alors : P(E) =,,,,,,} En comptant les éléments de P(E), on obtient : card(P(E)) = 23 = 8 Proposition 1.2. Si E est un ensemble fini de cardinal n, alors l’ensemble P(E) est fini et son cardinal est donné par : card(P(E)) = 2n 1.5 Les intervalles de R Définition 1.9 (Intervalle). Si I est une partie de R, on dit que I est un intervalle si pour tout x, y ∈ I, l’ensemble I contient tous les nombres réels compris entre x et y. — Intervalles fermés (contiennent leurs extrémités) : [a; b] = — Intervalles ouverts (ne contiennent aucune de leurs extrémités) : ]a; b[= — Intervalles semi-ouverts : [a; b[= (semi-ouvert à droite) ]a; b] = (semi-ouvert à gauche) Dr. BEHIANI Ridha Email: [email protected] Page 4/11.

Chapitre 1 : Analyse Combinatoire — Intervalles non bornés : [a; +∞[ = (fermé) ]a; +∞[ = (ouvert) ] − ∞; a] = (fermé) ] − ∞; a[ = (ouvert) Remarque 1.6. L’ensemble vide est un intervalle, on peut par exemple l’écrire ∅ =]1; 1[. R est lui-même un intervalle. On peut l’écrire R =] − ∞; +∞[. Exemple 1.9. Intersections d’intervalles : [2; 5]∩]3; 6] =]3; 5] ] − 1; 6] ∩ [2; +∞[ = [2; 6] [2; 4] ∩ [7; 10] = ∅ Union d’intervalles : [2; 15]∪]5; 32[ = [2; 32[ est un intervalle [2; 5]∪]15; 32[ n’est pas un intervalle 2 Analyse combinatoire L’analyse combinatoire a pour but le dénombrement des dispositions que l’on peut former à partir des éléments d’un ensemble de cardinal fini. Plus simplement, elle cherche à déterminer la manière de compter les objets ayant certaines propriétés. Les dispositions peuvent être : � ordonnes ou non ordonnes, avec ou sans rptition. On distingue trois types de dispositions :    Arrangement Permutation Combinaison avec ou sans répétition d’éléments 2.1 Principe fondamental de l’analyse combinatoire Théorème 2.1 (Principe fondamental). Si l’on considère une expérience composée de p choix indépendants, où : — le premier choix se fait parmi N1 éléments, — le deuxième choix parmi N2 éléments, Dr. BEHIANI Ridha Email: [email protected] Page 5/11.

Chapitre 1 : Analyse Combinatoire — . . ., — le p-ième choix parmi Np éléments, Alors le nombre total de résultats possibles est donné par : card(E) = N1 × N2 × · · · × Np Exemple 2.1. Vous achetez une valise à code 4 chiffres. Combien de possibilités avez-vous de choisir un code ? m = 4 avec N1 = 10, N2 = 10, N3 = 10, N4 = 10, donc le nombre total de codes possibles est : 10 × 10 × 10 × 10 = 104 = 10000 2.2 Arrangements Définition 2.1 (Arrangement sans répétition). On appelle arrangement sans répétition de p éléments parmi n éléments de l’ensemble E (p ≤ n), toute suite ordonnée et sans répétition de p éléments parmi n. Théorème 2.2. Le nombre d’arrangements de p éléments parmi n est : Ap n = n(n − 1) . . . (n − p + 1) = n! (n − p)! Remarque 2.1. n! = 1 × 2 × · · · × (n − 1) × n (factorielle n) n! = n(n − 1)! = n(n − 1)(n − 2)! = . . . (récursivité) n! ≈ √ 2πn �n e �n formule de Stirling 0! = 1 (par convention) Proposition 2.1 (Propriétés des arrangements). Pour tout n ∈ N∗ et tout p ∈ N avec p ≤ n : A1 n = n A0 n = 1 An n = n! Exemple 2.2. — Combien de nombres de deux chiffres distincts peut-on former avec les chiffres : 1, 2, 3, 4, 5. C’est un arrangement sans répétition de 2 éléments parmi 5 : A2 5 = 5! (5 − 2)! = 5! 3! = 3! × 4 × 5 3! = 4 × 5 = 20 On peut former 20 nombres de deux chiffres distincts. Dr. BEHIANI Ridha Email: [email protected] Page 6/11.

Chapitre 1 : Analyse Combinatoire — Nombre de nombres de 3 chiffres distincts formés à partir de : A3 9 = 9! (9 − 3)! = 504 nombres Définition 2.2 (Arrangement avec répétition). On appelle arrangement avec répétition de p éléments parmi n, toute suite ordonnée de p éléments choisis parmi n, avec possibilité de répétition d’un ou de plusieurs éléments. Théorème 2.3. Le nombre d’arrangements avec répétition de p objets parmi n est donné par : Ap n = np Exemple 2.3. — Combien de nombres de deux chiffres peut-on former avec les chiffres : 1, 2, 3, 4, 5. C’est un arrangement avec répétition de 2 éléments parmi 5 : A2 5 = 52 = 25 On peut former 25 nombres de deux chiffres. — Nombre de nombres de 3 chiffres formés à partir de : A3 9 = 93 = 729 nombres — Calculer le nombre de numéros de téléphones que peut attribuer un opérateur de télé- phonie mobile. Un numéro de téléphone mobile est composé de 10 chiffres : 0 X X X X X X X X X — Il commence toujours par 0 (chiffre fixe) — Le deuxième chiffre (X) indique l’opérateur (ex : Djezzy utilise 7) — Les huit chiffres suivants peuvent varier librement de 0 à 9 Si on fixe le préfixe "07", il reste 8 chiffres à composer. Chaque chiffre peut prendre 10 valeurs possibles : Nombre de possibilités = 108 = 100, 000, 000 2.3 Permutations Définition 2.3 (Permutation sans répétition). On appelle permutation sans répétition de n éléments distincts tout arrangement de n éléments parmi n. Ainsi le nombre de permu- tation de n éléments est donné par : Pn = n! Exemple 2.4. — Le nombre de permutations des lettres du mot IMAGE est : P5 = 5! = 120 Dr. BEHIANI Ridha Email: [email protected] Page 7/11.

Chapitre 1 : Analyse Combinatoire — Nombre de nombres de 3 chiffres formés avec (sans répétition) : 3! = 6 nombres Définition 2.4 (Permutation avec répétition). Le nombre de permutations de n éléments avec répétitions est donné par : P ′ n(r1, r2, · · · , rk) = n! r1! × r2! × · · · × rk! où r1, r2, · · · , rk désignent le nombre d’objets identiques. Exemple 2.5. — Nombre de nombres de 5 chiffres formés avec : 5! 2! × 2! = 30 nombres — Combien de façons différentes peut-on ranger les lettres du mot «MATHEMATIQUES» ? Le mot contient 11 lettres avec répétitions : — 2 «M», 2 «A», 2 «T», 2 «E» P11 = 11! 2! · 2! · 2! · 2! = 39916800 16 = 2494800 mots — Nombre de permutations des lettres du mot STATISTIQUES : P12(3, 3, 2) = 12! 3! × 3! × 2! = 6652800 2.4 Combinaisons sans répétition Définition 2.5 (Combinaison sans répétition). On appelle combinaison sans répétition de p éléments parmi n toute partie de E à p éléments. Théorème 2.4. Si on note Cp n le nombre de combinaisons de p éléments parmi n, alors : Cp n = n! (n − p)!p! = Ap n p! Exemple 2.6. — Nombre de façons de choisir 3 cartes dans un groupe de 8 cartes : C3 8 = 8! 3!(8 − 3)! = 56 — Nombre de sous-ensembles de 3 éléments de : C3 5 = 5! 3!(5 − 3)! = 10 — Dans une assemblée, il y a 10 hommes et 6 femmes : Dr. BEHIANI Ridha Email: [email protected] Page 8/11.

Chapitre 1 : Analyse Combinatoire — Groupements de 3 hommes : C3 10 = 10! 3!7! = 120 — Groupements de 2 femmes : C2 6 = 6! 2!4! = 15 — Groupements de 3 hommes et 2 femmes : C3 10 × C2 6 = 120 × 15 = 1800 — Dans une classe de 30 élèves, on doit élire deux délégués : C2 30 = 30! (30 − 2)!2! = 30! 28! × 2! = 28! × 29 × 30 28! × 2! = 29 × 30 2 = 29 × 15 = 435 Proposition 2.2 (Propriétés des combinaisons). Pour tout n ∈ N et tout p ∈ N avec p ≤ n : C0 n = Cn n = 1 C1 n = n Cp n = Cn−p n (Symétrie) Cp n = Cp n−1 + Cp−1 n−1 (Formule de Pascal) 2.5 Triangle de Pascal Proposition 2.3 (Relation de Pascal). Quels que soient les entiers n et p tels que 0 ≤ p ≤ n, on a l’égalité : Cp n = Cp n−1 + Cp−1 n−1 Démonstration. Cp−1 n−1 + Cp n−1 = (n − 1)! (p − 1)!(n − p)! + (n − 1)! p!(n − p − 1)! Or p! = (p − 1)! · p et (n − p)! = (n − p)(n − p − 1)! Donc : Cp−1 n−1 + Cp n−1 = (n − 1)!(p + n − p) p!(n − p)! = n! p!(n − p)! = Cp n Triangle de Pascal n \p 0 1 2 3 4 5 6 0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 5 1 5 10 10 5 1 6 1 6 15 20 15 6 1 2.6 Formule du binôme de Newton Théorème 2.5 (Binôme de Newton). Soient a et b deux nombres réels donnés non nuls. Pour tout entier naturel n, on a : (a + b)n = n � p=0 Cp nan−pbp Dr. BEHIANI Ridha Email: [email protected] Page 9/11.

Chapitre 1 : Analyse Combinatoire Démonstration. Développons les premières puissances : (a + b)0 = 1 = C0 0 (a + b)1 = 1a1b0 + 1a0b1 = C0 1a1b0 + C1 1a0b1 (a + b)2 = 1a2b0 + 2a1b1 + 1a0b2 = C0 2a2b0 + C1 2a1b1 + C2 2a0b2 (a + b)3 = 1a3b0 + 3a2b1 + 3a1b2 + 1a0b3 = C0 3a3b0 + C1 3a2b1 + C2 3a1b2 + C3 3a0b3 On constate que les coefficients du développement correspondent aux coefficients binomiaux. Pour tous nombres réels a et b donnés, non nuls, on a : (a − b)n = n � p=0 Cp n(−1)pan−pbp Exercice n°1 Donner les formes développées réduites des expressions suivantes. 1) A(x) = (1 + x)3 2) En déduire la forme développée réduite de B(x) = (1 − x)3 Solution. 1) A(x) = (1 + x)3 D’après la formule du binôme : (1 + x)3 = 3 � p=0 Cp 313−pxp = C0 3 + C1 3x + C2 3x2 + C3 3x3 = 1 + 3x + 3x2 + x3 2) B(x) = (1 − x)3 En remplaçant x par −x dans l’expression précédente : B(x) = 1 − 3x + 3x2 − x3 Exercice n°2 Donner la forme développée réduite de : C(x) = (3x − 2)4 Solution. C(x) = (3x − 2)4 = 4 � p=0 Cp 4(3x)4−p(−2)p Dr. BEHIANI Ridha Email: [email protected] Page 10/11.

Chapitre 1 : Analyse Combinatoire Calculons terme à terme : p = 0 : C0 4(3x)4(−2)0 = 1 · 81x4 · 1 = 81x4 p = 1 : C1 4(3x)3(−2)1 = 4 · 27x3 · (−2) = −216x3 p = 2 : C2 4(3x)2(−2)2 = 6 · 9x2 · 4 = 216x2 p = 3 : C3 4(3x)1(−2)3 = 4 · 3x · (−8) = −96x p = 4 : C4 4(3x)0(−2)4 = 1 · 1 · 16 = 16 Donc : C(x) = 81x4 − 216x3 + 216x2 − 96x + 16 Dr. BEHIANI Ridha Email: [email protected] Page 11/11.