Chapitres Maths en MPSI, PCSI, MP2I, PTSI

Cours : Dénombrements en Maths Sup

Name: Groupe Réussite: Cours particuliers, stages intensifs de révision
Brand: Groupe Réussite
SKU: Cours Particuliers
Rating: 4.9 (1012 reviews)

Résumé de cours Exercices et corrigés

Cours en ligne de Maths en Maths Sup

Résumé de cours et méthodes – Dénombrements en Maths Sup

Plan :

1. Démontrer qu’un ensemble est fini
2. Utiliser des ensembles finis dans des raisonnements
3. Récapitulatif des résultats
4. Quelle méthode utiliser ?

Retrouvez nos cours particuliers de maths à Paris en cas de lacune ou de perfectionnement de votre niveau en maths sup.

1. Pour démontrer qu’un ensemble est fini

$\bullet$ Si $E$ est non vide, démontrer qu’il existe un entier $n \in\mathbb{N}^*$ et une bijection de $[\![1,\, n]\!]$ sur $E$ .
Alors $n$ est unique et appelé cardinal de $E$ et noté $\# E = \textrm{Card }E = \vert E \vert$ .

$\bullet$ $\# \varnothing = 0$ .

$\bullet$ Démontrer qu’il existe une bijection $\varphi$ d’un ensemble fini $F$ sur $E$ .
Alors $E$ est fini et $\# E = \# F$ .

$\bullet$ Démontrer que $E$ est une partie d’un ensemble fini $F$ .
Alors $\# E \leq \# F$ .

$\bullet$ Démontrer que $E$ est la réunion de deux ensembles finis $A$ et $B$
$\ast$ Si $A \cap B = \varnothing,$ $\quad \quad \quad \# (A \cup B) = \# A + \# B$ .
$\ast$ Si $A \cap B \neq \varnothing$ ,
$\# (A \cup B) = \# A + \# B - \# (A \cap B)$ .

$\bullet$ Démontrer que $E = A \times B$ avec $A$ et $B$ finis :
$\quad \quad \# (A \times B) = \# A \, \times \, \# B$ .

$\bullet$ Plus généralement si $n \in \mathbb{N}, n\geq 3$ et si $E = \displaystyle \prod _{i = 1} ^n A_i$ où $\forall\, i \in [\![1 ,\, n]\!],\, A _ i$ est fini, $E$ est fini et $\quad \quad \displaystyle \# \left ( \prod _{i = 1} ^n A_i \right ) = \prod _{i = 1} ^n \left ( \# A_i \right)$ .

Exercice
Si $A,\, B,\, C$ sont trois parties de l’ensemble fini $E$ , calculer $\quad \quad \quad \# (A \cup B \cup C)$ .

Démo : On utilise le cardinal d’une réunion de deux ensembles avec $A \cup B$ et $C$ et
$(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$ .

$\# (A \cup B \cup C) = \# ((A \cup B) \cup C)$
$= \# (A \cup B) + \# C - \# ((A \cup B) \cap C)$
$= \# (A \cup B) + \# C - \# ((A \cap C) \cup (B \cap C))$
On réutilise la formule donnant le cardinal de la réunion de deux ensembles et la relation :
$\quad \; (A \cap C) \cap (B \cap C) = A \cap B \cap C$ .

$\# (A \cup B \cup C) = \# A + \# B - \# (A \cap B)$
$\quad +\, \# C - \# (A \cap C) - \# (B \cap C)$ $\quad \quad \quad \quad +\, \# ( A \cap B \cap C)$
et en réordonnant :
$\# (A \cup B \cup C)= \#A + \#B + \# C$ $\quad - \, \# (A \cap B) - \# (A \cap C) - \# (B \cap C)$ $\quad \quad \quad \quad + \, \# (A \cap B \cap C)$ .

COURS DE MATHS A DOMICILE

Les meilleurs profs de maths pour
réussir sa scolarité

En ligne ou à domicile

Avis Google France ★★★★★ 4,9 sur 5

2. Utiliser des ensembles finis dans des raisonnements

$\bullet$ Si $E$ et $F$ sont deux ensembles finis de même cardinal et $\varphi$ est une application de $E$ dans $F$ ,
$\varphi$ est bijective ssi $\varphi$ est injective ssi $\varphi$ est surjective.

$\bullet$ Si $E$ et $F$ sont deux ensembles finis, pour démontrer que $E$ = $F$ , il suffit de prouver une inclusion et que $E$ et $F$ ont même cardinal.

$\bullet$ Si $A$ est une partie de l’ensemble fini $E$ , son complémentaire $\overline{A} = C_E A$ est fini et $\# \overline{A} = \# E - \# A$ .

3. Récapitulatif des résultats

Dans la suite, $n$ et $p$ sont des entiers non nuls et $E_n$ est un ensemble de cardinal $n$ .

$\bullet$ $n^p$ est le nombre
$\ast$ de choix successifs avec remise de $p$ éléments de $E_n$
$\ast$ de listes avec répétition de $p$ éléments de $E_n$
$\ast$ d’applications de $E_p$ dans $E_n\,$ .
l’ordre des éléments a de l’importance !

$\bullet$ Si $p \leq n$ , $\displaystyle A_n^p = \frac {n!} {(n - p)!}$ est le nombre
$\ast$ de choix successifs sans remise de $p$ éléments de $E_n$
$\ast$ de listes de $p$ éléments distincts de $E_n$
$\ast$ d’applications injectives de $E_p$ dans $E_n\,$ .
les éléments sont choisis les uns après les autres et les $p$ éléments choisis sont distincts.

$\bullet$ Si $p \leq n$ , $\displaystyle {\binom {n} {p}} = \displaystyle \frac{n!} {p! \, (n - p)!}$ est le nombre
$\ast$ de choix simultanés sans remise de $p$ éléments de $E_n$
$\ast$ de listes strictement croissantes de $p$ éléments de $[\![1 , n]\!]$ (h.p. voir dem plus bas )
$\ast$ de parties à $p$ éléments de $E_n$ (ou $p-$ combinaisons).
Les éléments sont choisis en même temps. Les $p$ éléments choisis n’ont pas d’ordre.

Exercice Nombre de listes strictement croissantes de $p$ éléments de $[\![1 , n]\!]$ .

Correction : On suppose $p \leq n$ et on note $\mathcal{S}_{p,n}$ l’ensemble $\{(i_1\, ,\, \cdots \, , \, i_p) \in\mathbb{N}^{*p}\, / \, i_1 < \, \cdots \, < i_p \leq n \}$ et $\mathcal{P}_p(n)$ l’ensemble des parties de $[[1 , n]]$ à $p$ éléments.
L’application $\mathcal{S}_{p,n} \to \mathcal{P}_p(n)$ $\quad \quad (i_1 \, ,\, \cdots \, , \, i_p ) \mapsto \{i_1 ,\, \cdots \, , \, i_p \}$
est une bijection (toute partie finie peut être rangée d’une unique façon sous forme strictement croissante), donc $\quad \quad \# \mathcal{S}_{p,n} = \# \mathcal{P}_p(n) = \displaystyle {\binom {n} {p} }$ .

Résultats à savoir démontrer :
si $n \in \mathbb{N}$ et $n \geq 2$ ,
$\# \{ (i , \, j) \in \mathbb{N}^2 \, / \, 1 \leq i < j \leq n \}$ $\quad \quad \quad \quad \quad \quad \quad \quad = \displaystyle \frac {n(n - 1)} 2$ .
$\# \{ (i , \, j) \in \mathbb{N}^2 \, / \, 1 \leq i \leq j \leq n \}$ $\quad \quad \quad \quad \quad \quad \quad \quad = \displaystyle \frac {n(n + 1)} 2$ .

Correction :

Soit $\mathcal{P}_2(n)$ l’ensemble des parties de $[[1 , n]]$ à $2$ éléments.

$\ast$ $S = \{ (i , \, j) \in \mathbb{N}^2 \, / \, 1 \leq i \leq j \leq n \}$ .
L’application $\mathcal{S} \to \mathcal{P}_2(n)$ $\quad \quad \quad \quad \quad (i \, ,\, j ) \mapsto \{i ,\,j\}$
est une bijection (toute partie finie peut être rangée d’une unique façon sous forme strictement croissante), donc $\quad \# \mathcal{S} = \# \mathcal{P}_2(n) = \displaystyle {\binom {n} {2} } = \frac {n(n - 1)}2$ .

$\ast$ $C = \{ (i , \, j) \in \mathbb{N}^2 \, / \, 1 \leq i \leq j \leq n \}$
On écrit $C = S \cup E$ avec $\quad \quad \quad E = \{ (i , \, i) \, / \, 1 \leq i \leq n \}$

Comme $S \cap E = \varnothing$ , $\# C = \# S + \# E = \displaystyle \frac {n(n - 1)} 2 + n$
$\# C = \displaystyle \frac {n(n + 1)} 2$

$\bullet$ Si $E$ est un ensemble fini de cardinal $n$ , $\mathcal{P}(E)$ est fini de cardinal $2^n$ .

En connaître 2 démonstrations :

$\bullet$ Première démonstration.
Soit $E$ un ensemble fini à $n$ éléments.
On écrit $\mathcal{P}(E) = \displaystyle \bigcup_{k = 0} ^n \mathcal {P} _ k(E)$
en notant $\mathcal {P} _ k(E)$ l’ensemble des parties de $E$ à $k$ éléments.
On introduit ainsi une partition de $\mathcal{P}(E)$
donc $\# \mathcal{P}(E) = \displaystyle \sum _{k = 0} ^n \# \mathcal{P}_k(E)$
$\# \mathcal{P}(E) = \displaystyle \sum _ {k = 0} ^n \binom {n} k$
$\# \mathcal{P}(E) = \displaystyle \sum _ {k = 0} ^n \binom {n} k \, 1 ^k \, 1^ {n - k} = (1 + 1) ^n$
par le binôme de Newton.

$\bullet$ Deuxième démonstration.
Si $\# E_n = n$ , on note $p_n = \# \mathcal{P}(E_n)$ .
$\ast$ $p_0 = 1$ car $\mathcal{P} (\varnothing) = \{ \varnothing \}$ .

$\ast$ Relation entre $p_{n + 1}$ et $p_n\,$ .
Soit $a \in E_{n + 1}$ et $E_n = E_{n + 1} \setminus \{a \}$ .
On note $\mathcal{P}(E_{n + 1} ) = \mathcal{A} \cup \mathcal{B}$
en notant $\mathcal{A} = \{ X \subset E_{n + 1} \, / \, a \in X \}$
et $\mathcal{B} = \{ X \subset E_{n + 1} \, / \, a \notin X \}$
$\mathcal{A}$ et $\mathcal{B}$ sont disjoints.

$\mathcal{B} = \mathcal{P} (E_n)$ donc $\# \mathcal{B} = \# \mathcal{P}(E_n) = p_n\,$ .

$\varphi : \mathcal{P}(E_n) \to \mathcal{A}, X \mapsto X \cup \{a \}$ est une bijection, donc $\# \mathcal{P}(E_n)= \# \mathcal{A}$

alors $\# \mathcal{P}(E_{n + 1} ) = \# \mathcal{A} + \# \mathcal{B}$
donne $p_{n + 1} = 2 \, p_n$

$\ast$ $(p_n)_n$ est une suite géométrique de raison 2 et de premier terme $p_0 = 1$
alors $p_n = 2 ^n$ .
$\bullet$ Et une troisième démonstration.
On rappelle que l’on note $\textbf{1}_A$ la fonction indicatrice de l’ensemble $A$ .
L’application $\varphi : \mathcal{P} (E) \to \mathcal{F} ( E, \{ 0, 1 \} )$ , $A \mapsto \textbf{1}_A$ est une bijection, donc
$\quad \quad \# \mathcal{P} (E) = \# \mathcal{F} ( E, \{ 0, 1 \} ) = 2 ^n$ .

UN PROF DE MATHS POUR EXCELLER

La pratique et la compréhension
clés de la réussite

Cours de maths en ligne ou à domicile

Avis Google France ★★★★★ 4,9 sur 5

4. Quelle méthode utiliser ?

4.1. Règle du produit
Si l’on doit choisir un premier élément de $n_1$ façons, un deuxième élément de $n_2$ façons , … , et le $p$ – ième élément de $n_p$ façons,
le nombre de choix possibles est égal à $n_1\, n_2\, \cdots \,n_p\,$ .
c’est en effet le nombre d’éléments de $A_1 \times A_2 \, \cdots \, A_p$ où $A_i$ est l’ensemble dans lequel on choisit le $i$ -ème élément.

4.2. Utilisation d’une réunion
Si l’on doit choisir un élément vérifiant une propriété $P_1$ ou un élément vérifiant une propriété $P_2$ :
On note $A$ (resp $B$ ) l’ensemble des éléments vérifiant $P_1$ (resp $P_2$ ).
$\ast$ Dans le cas où il n’y a aucun élément vérifiant les propriétés $P_1$ et $P_2$ en même temps :
$\quad \quad \# (A \cup B) = \# A + \# B$
car $A \cap B = \varnothing$ .
$\ast$ Dans le cas où il y a des éléments vérifiant les propriétés $P_1$ et $P_2$ en même temps :
$\# (A \cup B) = \# A + \# B - \# (A \cap B)$ .

4.3. Utilisation d’une partition
Pour justifier $\displaystyle \# A = \sum _{k = 0} ^n \# A_k\,$ , commencer par prouver que la famille $(A_k)_{0\leq k\leq n }$ est une partition de $A$ (parties non vides, deux à deux disjointes, de réunion égale à $A$ ).
Puis $\displaystyle \# \bigcup _{k = 0} ^n A_k = \sum _{k = 0} ^n \# A_k\,$ .

4.4. « avoir au moins un élément vérifiant une propriété $\mathcal{P}$ «
$\ast$ Pour dénombrer un problème contenant un « au moins », en général il est plus simple de dénombrer le complémentaire (c’est le cas lorsque le complémentaire se traduit par « sans »).
$\ast$ Lorsque le nombre maximum $M$ d’éléments vérifiant la propriété est faible, on peut envisager de noter $B _ k$ « avoir $k$ éléments vérifiant $\mathcal{P}$ » et écrire $A = \displaystyle \bigcup_{k = 1} ^{M} B_k$ , les ensembles étant deux à deux disjoints, $\#A = \displaystyle \sum _ {k = 1} ^M \# B_k \,$

4.5. Calculer $\# A \cap B$ où $A$ et $B$ sont deux parties de $E$ et $B$ définie par « avoir au moins un élément vérifiant $\mathcal{P}$ »
Utiliser $A = A \cap E = A \cap (B \cup \overline {B})$
$A = (A \cap B) \cup (A \cap \overline {B})$ .
Les deux ensembles étant disjoints :
$\quad \# A = \# (A \cap B) + \#(A \cap \overline {B})$
et utiliser $\quad \# (A \cap B) = \# A - \#(A \cap \overline {B})$
pour répondre à la question.

Les cours en ligne de Maths Sup sont parfaits pour prendre de l’avance en mathématiques en MPSI, PCSI et PTSI. Ainsi, vous pouvez accéder dès maintenant aux chapitres suivants :

Cours : Dénombrements en Maths Sup

Résumé de cours et méthodes – Dénombrements en Maths Sup

Plan :

1. Pour démontrer qu’un ensemble est fini

COURS DE MATHS A DOMICILE

Les meilleurs profs de maths pour
réussir sa scolarité

En ligne ou à domicile

2. Utiliser des ensembles finis dans des raisonnements

3. Récapitulatif des résultats

UN PROF DE MATHS POUR EXCELLER

La pratique et la compréhension
clés de la réussite

Cours de maths en ligne ou à domicile

4. Quelle méthode utiliser ?

Contact

Qui sommes-nous ?

Nous rejoindre

Copyright @ GROUPE REUSSITE - Mentions légales

Cours : Dénombrements en Maths Sup

Résumé de cours et méthodes – Dénombrements en Maths Sup

Plan :

1. Pour démontrer qu’un ensemble est fini

COURS DE MATHS A DOMICILE

Les meilleurs profs de maths pour réussir sa scolarité

En ligne ou à domicile

2. Utiliser des ensembles finis dans des raisonnements

3. Récapitulatif des résultats

UN PROF DE MATHS POUR EXCELLER

La pratique et la compréhension clés de la réussite

Cours de maths en ligne ou à domicile

4. Quelle méthode utiliser ?

Contact

Qui sommes-nous ?

Nous rejoindre

Copyright @ GROUPE REUSSITE - Mentions légales

Les meilleurs profs de maths pour
réussir sa scolarité

La pratique et la compréhension
clés de la réussite