Chapitre 03
Dénombrement
I. Ensembles finis I.2. Parties d'un ensemble fini
I.1. Cardinal d'un ensemble fini
Théorème 2
Définition 1
Soit E un ensemble fini et F ⊂ E. Alors :
Un ensemble E est fini s’il est vide ou s’il existe 𝒏 ∈ ℕ tel que ⟦𝟏, 𝒏⟧ soit en bijection avec E.
∗
F est fini et Card (F) ≤ Card (E).
Un ensemble qui n’est pas fini est dit infini. Si de plus Card (F) = Card (E), alors F = E.
Méthode
Pour montrer que deux ensembles finis sont égaux, il suffit de montrer qu’ils ont le même cardinal et que l’un est
Proposition 1
inclus dans l’autre.
Pour tous 𝒑, 𝒒 ∈ ℕ∗ , on a l’équivalence :
il existe une application injective de ⟦𝟏, 𝒑⟧ dans ⟦𝟏, 𝒒⟧ ⟺ 𝒑 ≤ 𝒒. I.3. Opérations sur les ensembles finis
Proposition 3
Proposition 2
Si A et B sont deux ensembles finis et disjoints, alors
Pour tous 𝒑, 𝒒 ∈ ℕ∗ , on a l’équivalence : A ∪ B est fini et Card (A ∪ B) = Card (A) + Card (B).
il existe une application surjective de ⟦𝟏, 𝒑⟧ dans ⟦𝟏, 𝒒⟧ ⟺ 𝒑 ≥ 𝒒.
Corollaire 2
Corollaire 1
Si E est un ensemble fini et A est une partie de E, alors
Pour tous 𝒑, 𝒒 ∈ ℕ , on a l’équivalence :
∗ Card (A𝒄 ) = Card (E) − Card (A) avec A𝒄 est le complémentaire de A dans E.
il existe une application bijective de ⟦𝟏, 𝒑⟧ dans ⟦𝟏, 𝒒⟧ ⟺ 𝒑 = 𝒒.
Corollaire 3
Théorème 1
Si A et B sont deux ensembles finis, alors
Soit E un ensemble fini et non vide. A ∪ B est fini et Card (A ∪ B) = Card (A) + Card (B) − Card (A ∩ B).
Il existe un unique entier naturel non nul 𝒏 tel que ⟦𝟏, 𝒏⟧ soit en bijection avec E.
Cet entier est appelé le cardinal (ou nombre d’éléments) de E et se note Card(E) ou ȁEȁ.
Proposition 4
Conventions
Si A𝟏 , … , A𝒏 sont des ensembles finis, alors
• Card(∅) = 𝟎. 𝒏 𝒏 𝒏
• Si E est un ensemble infini, on pose Card(E) = +∞. ⋃ A𝒌 est fini et Card ( ⋃ A𝒌 ) ≤ ∑ Card(A𝒌 )
𝒌=𝟏 𝒌=𝟏 𝒌=𝟏
Remarque 1 avec égalité si, et seulement si, A𝟏 , … , A𝒏 sont deux à deux disjoints.
Si E est un ensemble fini non vide de cardinal 𝒏, il existe une application bijective 𝒊 ⟼ 𝒂𝒊
de ⟦𝟏, 𝒏⟧ dans E (ce qui permet de numéroter les éléments de E), donc E = {𝒂𝟏 , 𝒂𝟐 , … , 𝒂𝒏 }. Remarque 2
Exemple 1 Plus précisément, si A𝟏 , … , A𝒏 sont des ensembles finis, alors
Soit 𝑝, 𝑛 ∈ ℤ tels que 𝑝 ≤ 𝑛.
𝒏 𝒏
Card ( ⋃ A𝒌 ) = ∑ (−𝟏)
𝒌−𝟏
∑ Card (⋂ A𝒊 ) (Formule du crible) .
Card (⟦𝑝, 𝑛⟧) = 𝑛 − 𝑝 + 1 car l’application 𝑘 ⟼ 𝑘 + 𝑝 − 1 est bijective de ⟦1, 𝑛 − 𝑝 + 1⟧ dans ⟦𝑝, 𝑛⟧. 𝒌=𝟏 𝒌=𝟏 I∈P 𝒌(⟦𝟏,𝒏⟧) 𝒊∈I
I.4. Applications entre ensembles finis II. Exemples usuels de dénombrement
II.1. Nombre de 𝒏 - uplets
Proposition 5
Si 𝒇 est une application définie sur un ensemble fini E, alors Proposition 7
𝒇 (E) est fini et Card (𝒇(E)) ≤ Card (E) Si E𝟏 , … , E𝒏 sont des ensembles finis, alors
avec égalité si et seulement si 𝒇 est injective. 𝒏 𝒏 𝒏
le produit cartésien ෑ E𝒊 est fini et Card (ෑ E𝒊) = ෑ Card(E𝒊 ) .
𝒊=𝟏 𝒊=𝟏 𝒊=𝟏
Proposition 6 Intuitivement : pour former un 𝑛 - uplet (𝑥1 , … , 𝑥𝑛 ), on peut passer par les étapes suivantes :
• on choisit une valeur de 𝑥1 dans E1 : il y a Card (E1 ) choix possibles,
Soit E et F deux ensembles finis et 𝒇 ∈ F (E, F).
• on choisit une valeur de 𝑥2 dans E2 : il y a Card (E2 ) choix possibles,
• Si 𝒇 est injective, alors Card (E) ≤ Card (F).
⋮
• Si 𝒇 est surjective, alors Card (E) ≥ Card (F). • on choisit une valeur de 𝑥1 dans E𝑛 : il y a Card (E𝑛 ) choix possibles.
• Si 𝒇 est bijective, alors Card (E) = Card (F).
Il y a donc Card (E1 ) × … × Card (E𝑛 ) éléments de E1 × … × E𝑛 .
Remarque 3 Exemple 3
𝑛
Pour calculer le cardinal d’un ensemble E, il suffit d’exhiber un ensemble F de cardinal connu qui soit en bijection Si 𝑛 ∈ ℕ∗ et E est un ensemble fini, alors Card (E𝑛 ) = (Card(E)) .
avec E.
II.2. Nombre d'applications entre deux ensembles finis
Théorème 3
Proposition 8
Soit E et F deux ensembles finis de même cardinal et 𝒇 ∈ F (E, F).
Il y a équivalence entre : • 𝒇 est bijective, Si E et F sont des ensembles finis, alors
• 𝒇 est injective, F (E, F) est fini et Card (F (E, F)) = Card(F)Card(E).
• 𝒇 est surjective.
Intuitivement : Notons E = {𝑥1 , … , 𝑥𝑝 } et 𝑛 = Card (F). Pour former une application 𝑓 : E ⟶ F, on peut passer
par les étapes : • on choisit une valeur de 𝑓(𝑥1 ) dans F : il y a 𝑛 choix possibles,
Corollaire 4 • on choisit une valeur de 𝑓(𝑥2 ) dans F : il y a 𝑛 choix possibles,
⋮
Soit E un ensemble fini et 𝒇 ∈ F (E,E). Il y a équivalence entre : • 𝒇 est bijective, • on choisit une valeur de 𝑓(𝑥𝑝 ) dans F : il y a 𝑛 choix possibles.
• 𝒇 est injective, Il y a donc ⏟
𝑛 × … × 𝑛 = 𝑛𝑝 applications de E dans F.
• 𝒇 est surjective. 𝑝 𝑓𝑜𝑖𝑠
Attention II.3. Nombre de parties d'un ensemble fini
Ce résultat est faux si E est infini.
Par exemple, l’application ℕ ⟶ ℕ est injective et non surjective. Proposition 9
𝑛 ⟼ 2𝑛
Si E est un ensembles fini, alors
Exemple 2 P (E) est fini et Card (P (E)) = 𝟐Card(E) .
Soit (A, +,×) un anneau fini et intègre et 𝑎 ∈ A\{0A }. Considérons l’application 𝜑 : A ⟶ A
𝑥 ⟼ 𝑎𝑥
Pour tout (𝑥, 𝑦) ∈ A2 , on a 𝜑(𝑥) = 𝜑(𝑦) ⟹ 𝑎(𝑥 − 𝑦) = 0A Démonstation :
⟹ 𝑥 − 𝑦 = 0A (car A est intègre et 𝑎 ≠ 0A ) Il suffit de montrer que l’application P (E) ⟶ F (E, {0,1}) est bijective.
⟹ 𝑥=𝑦 A ⟼ 𝟙A
donc 𝜑 est injective, et puisque A est fini, alors 𝜑 est bijective. (𝟙A est la fonction indicatrice de A).
II.4. Nombre d'arrangements ou d'injections II.5. Nombre de combinaisons
Définition 2 Définition 3
Soit E un ensemble et 𝒑 ∈ ℕ∗ . Soit un ensemble et 𝒑 ∈ ℕ.
On appelle 𝒑 – arrangement d’éléments de E tout 𝒑 – uplet (𝒙𝟏 , … , 𝒙𝒑 ) d’éléments de E deux à deux distincts On appelle 𝒑 – combinaison d’éléments de E toute partie à 𝒑 éléments de E.
(c’est-à-dire 𝒙𝒊 ≠ 𝒙𝒋 pour tous 𝒊 ≠ 𝒋).
Proposition 11
Proposition 10
Soit 𝒑 ∈ ℕ et E un ensemble fini de cardinal 𝒏.
Soit 𝒑 ∈ ℕ et E un ensemble fini de cardinal 𝒏.
∗
A𝒑𝒏
𝒏!
si 𝒑 ≤ 𝒏
Le nombre de 𝒑 – combinaison d’éléments de E est C𝒏 =
𝒑
𝒏! = ቐ𝒑! (𝒏 − 𝒑)! .
si 𝒑 ≤ 𝒏 𝒑!
Le nombre de 𝒑 – arrangement d’éléments de E est A𝒏 = ቐ(𝒏 − 𝒑)!
𝒑
. 𝟎 si 𝒑 > 𝒏
𝟎 si 𝒑 > 𝒏
Intuitivement : pour former un 𝑝 – arrangement (𝑥1 , … , 𝑥𝑝 ) (avec 1 ≤ 𝑝 ≤ 𝑛), on peut passer par les étapes :
Intuitivement : pour former un 𝑝 – arrangement (𝑥1 , … , 𝑥𝑝 ) (avec 1 ≤ 𝑝 ≤ 𝑛), on passe par les étapes : • on choisit une partie A à 𝑝 éléments de E : il y a alors C𝑛𝑝 choix possibles,
• on choisit une valeur de 𝑥1 : il y a alors 𝑛 choix possibles, • une fois A est fixée, on forme le 𝑝 – arrangement (𝑥1 , … , 𝑥𝑝 ) : on peut former A𝑝𝑝 = 𝑝!.
• on choisit une valeur de 𝑥2 : il n’y a que 𝑛 − 1 choix possibles, Il y a alors 𝑝! × C𝑛𝑝 𝑝 – arrangements d’éléments de E, donc A𝑝𝑛 = 𝑝! × C𝑛𝑝 .
⋮
• on choisit une valeur de 𝑥𝑝 : il y a 𝑛 − (𝑝 − 1) choix possibles. Exemple 4
Il y a donc 𝑛 × (𝑛 − 1) × … × (𝑛 − 𝑝 + 1) 𝑝 – arrangements d’éléments de E. Soit E un ensemble de cardinal 𝑛.
Pour tout 𝑘 ∈ ⟦0, 𝑛⟧, on pose P𝑘 (E) = {A ∈ P (E)⁄Card(A) = 𝑘}.
Convention La famille (P𝑘 (E))0≤𝑘≤𝑛 est une partition de P (E), donc
On pose A𝟎𝒏 = 𝟏. 𝑛 𝑛 𝑛
𝑘
Card (P (E)) = Card ( ⋃ P𝑘 (E)) = ∑ Card ( P𝑘 (E)) = ∑ C𝑛 .
𝑘=0 𝑘=0 𝑘=0
Remarque 3 𝑛
Et puisque Card (P (E)) = 2 , alors
𝑛 𝑘
∑ C𝑛 = 2𝑛.
La formule établie dans la proposition 10 reste alors valable pour 𝑝 = 0. 𝑘=0
Corollaire 5 Proposition 12
Soit E et F deux ensembles finis. Pour tous entiers 𝒌 et 𝒏 tels que 𝟎 ≤ 𝒌 ≤ 𝒏, on a C𝒏𝒌 = C𝒏𝒏−𝒌.
L’ensemble I (E, F) des applications injectives E dans F est fini et Card (I (E, F)) = ACard
(E)
Card(F) .
Pour la démonstration, il suffit de montrer que l’application P𝑘 (⟦1, 𝑛⟧) ⟶ P𝑛−𝑘 (⟦1, 𝑛⟧) est bijective.
A ⟼ C⟦1,𝑛⟧ A
Corollaire 6
Soit E et F deux ensembles finis de même cardinal 𝒏.
Proposition 13 Formule de Pascal
L’ensemble B (E, F) des applications bijectives de E dans F est fini et Card (B (E, F)) = 𝒏!.
Pour tous entiers 𝒌 et 𝒏 tels que 𝟎 ≤ 𝒌 ≤ 𝒏, on a C𝒏𝒌 + C𝒏𝒌+𝟏 = C𝒏+𝟏
𝒌+𝟏
.
Corollaire 7 Démonstration : en fixant 𝑝 ∈ ⟦1, 𝑛 + 1⟧, on obtient P𝑘+1 (⟦1, 𝑛 + 1⟧) = A ∪ B avec
- A = {X ∈ P𝑘+1 (⟦1, 𝑛 + 1⟧)⁄𝑝 ∈ X} : Card (A) = C𝑛𝑘 ,
Soit E un ensemble fini de cardinal 𝒏.
- B = {X ∈ P𝑘+1 (⟦1, 𝑛 + 1⟧)⁄𝑝 ∉ X} : Card (B) = C𝑛𝑘+1 .
µ
L’ensemble S(E) des permutations de E est fini et Card (S(E)) = 𝒏!.
Donc C𝑛+1
𝑘+1
= Card (P𝑘+1 (⟦1, 𝑛 + 1⟧)) = Card (A) + Card (B) = C𝑛𝑘 + C𝑛𝑘+1 .
III. Ensembles dénombrables III.2. Opérations sur les ensembles au plus dénombrables
III.1. Définitions et propriétés
Proposition 16
Définition 4
Soit E𝟏 , … , E𝒏 des ensembles au plus dénombrables.
𝒏
Un ensemble est dit dénombrable s’il est en bijection avec ℕ. • Le produit cartésien ෑ E𝒊 est au plus dénombrable.
𝒊=𝟏
𝒏
• S’il y a un ensemble E𝒊 dénombrable et si les autres sont non vides. alors ෑ E𝒊 est dénombrable.
Remarque 4 𝒊=𝟏
• Tout ensemble dénombrable peut s’écrire sous la forme {𝒙𝒏 ⁄ 𝒏 ∈ ℕ} avec 𝒙𝒏 ≠ 𝒙𝒎 si 𝒏 ≠ 𝒎.
• Intuitivement, un ensemble dénombrable est un ensemble infini que l’on peut numéroter ses éléments. Exemple 8
L’application ℤ × ℕ∗ ⟶ ℚ est surjective et ℤ × ℕ∗ est dénombrable (comme produit de deux ensembles
Exemple 5 (𝑝, 𝑞) ⟼ 𝑝⁄𝑞
ℤ est dénombrable car l’application ℕ ⟼ ℤ est bijective. dénombrables), donc ℚ est au plus dénombrable. Comme ℚ est infini, il est alors dénombrable.
𝑛⁄2 si 𝑛 est pair
𝑛 ⟼{
− (𝑛 + 1)⁄2 si 𝑛 est impair Exemple 9
Exemple 6 Soit 𝑛 ∈ ℕ. ℚ𝑛 [X] est dénombrable car l’application ℚ𝑛+1 ⟼ ℚ𝑛 [X]
(𝑎0 , … , 𝑎𝑛 ) ⟼ 𝑎0 + 𝑎1 X + ⋯ + 𝑎𝑛 X𝒏
ℕ est dénombrable car l’application ℕ ⟼ ℕ
∗ ∗
est bijective.
𝑛 ⟼𝑛+1 est bijective et ℚ𝑛+1 est dénombrable comme produit cartésien d’ensembles dénombrables.
Définition 5 Proposition 17
Un ensemble est dit au plus dénombrable s’il est est fini ou dénombrable. Soit (E𝒊 )𝒊∈I une famille au plus dénombrable d’ensembles au plus dénombrables.
• La réunion ⋃ E𝒊 est au plus dénombrable.
𝒊∈I
• S’il existe un ensemble E𝒊 dénombrable, alors la réunion est dénombrable.
Proposition 14
Exemple 10
• Toute partie de ℕ est au plus dénombrable.
On a : - ℚ[X] = ⋃ ℚ𝑛 [X] ;
• Un ensemble est au plus dénombrable si et seulement s’il est en bijection avec une partie de ℕ. 𝑛∈ℕ
- ℚ𝑛 [X] est dénombrable pour tout 𝑛 ∈ ℕ.
Donc ℚ [X] est dénombrable (comme réunion dénombrable d'ensembles dénombrables).
Proposition 15
III.3. Exemples d'ensembles infinis non dénombrables
Soit E un ensemble non vide. Les propriétés suivantes sont équivalentes :
• E est au plus dénombrable ; Proposition 18
• il existe une injection de E dans ℕ ;
Pour tout ensemble E, il n’existe aucune application surjective de E dans P (E).
• il existe une surjection de ℕ dans E ;
• il existe une surjection d’un ensemble au plus dénombrable dans E.
En effet, pour toute application 𝜑 : E ⟶ P (E), la partie {𝑥 ∈ E ⁄𝑥 ∉ 𝜑(𝑥)} n’a pas d’antécédent par 𝜑.
Exemple 7 Exemple 11
ℕ𝟐 est dénombrable car il est infini et l’application ℕ𝟐 ⟶ ℕ est injective. P (ℕ) est un ensemble infini non dénombrable.
(𝑝, 𝑞) ⟼ 2𝑝 3𝑞
Exemple 12
Corollaire 8 L’application P (ℕ) ⟶ F (ℕ, {0,1}) est bijective, donc F (ℕ, {0,1}) est infini non dénombrable.
A ⟼ 𝟙A
Toute partie d’un ensemble au plus dénombrable est au plus dénombrable. Exemple 13
On peut aussi démontrer que les ensembles ℝ et P (ℝ) sont non dénombrables.
