Dénombrement

Preuve.

1. On pose : $A = \{x_1; x_2; \dots; x_n\}$ et $B = \{y_1; y_2; \dots; y_p\}$.
   • Si $A \cap B = \emptyset$ alors $A \cup B = \{x_1; x_2; \dots; x_n; y_1; y_2; \dots; y_p\}$, donc le nombre d'éléments de $A \cup B$ est $n + p$, c'est-à-dire que : $\text{Card}(A \cup B) = n + p = \text{Card } A + \text{Card } B$
   • Si $A \cap B \neq \emptyset$ alors on pose : $X = A \setminus (A \cap B)$ et $Y = B \setminus (A \cap B)$. Puisque $X$ et $A \cap B$ sont disjoints, alors : $\text{Card } X = \text{Card } A – \text{Card}(A \cap B)$. De même, $Y$ et $A \cap B$ sont disjoints, alors : $\text{Card } Y = \text{Card } B – \text{Card}(A \cap B)$. Puisque les ensembles $X$, $Y$ et $A \cap B$ sont deux à deux disjoints, alors :
     \[\begin{aligned}\text{Card}(A \cup B) &= \text{Card } X + \text{Card } Y + \text{Card}(A \cap B) \\ &= \text{Card } A – \text{Card}(A \cap B) + \text{Card } B – \text{Card}(A \cap B) + \text{Card}(A \cap B) \\ &= \text{Card } A + \text{Card } B – \text{Card}(A \cap B)\end{aligned}\]
2. Si $A \subset E$ alors : $E = A \cup C_E^A$. Puisque $A \cap C_E^A = \emptyset$, alors : $\text{Card } E = \text{Card } A + \text{Card}(C_E^A)$. Par conséquent : $\text{Card } A \le \text{Card } E$. Si $\text{Card } A = \text{Card } E$ alors $\text{Card}(C_E^A) = 0$, d'où : $C_E^A = \emptyset$. Par suite : $A = E$.

Preuve. On suppose que : $\text{Card } E = p$ et $\text{Card } F = n$. Posons : $E = \{x_1; x_2; \dots; x_p\}$ et $F = \{y_1; y_2; \dots; y_n\}$. Soit $(x_i ; y_j)$ un élément de $E \times F$ tel que $i \in \{1; \dots; p\}$ et $j \in \{1; \dots; n\}$. Le nombre de choix de $x_i$ est $p$ et le nombre de choix de $y_j$ est $n$. D'après le principe fondamental du dénombrement, le nombre de choix de couples $(x_i ; y_j)$ est $pn$. Par suite :

Preuve. Posons : $E = \{x_1 ; x_2 ; \dots ; x_p\}$. Construire une application de $E$ dans $F$ revient à :

• Choisir l'élément $f(x_1)$ dans $F$ : $n$ choix possibles.
• Choisir l'élément $f(x_2)$ dans $F$ : $n$ choix possibles.
• $\dots$
• Choisir l'élément $f(x_p)$ dans $F$ : $n$ choix possibles.

D'après le principe fondamental du dénombrement, il existe $\underbrace{n \times n \times \dots \times n}_{p \text{ fois}} = n^p$ choix possibles.

Preuve. Raisonnons par récurrence sur l'entier $n$.

• Pour $n = 0$, le seul ensemble à étudier est $E = \emptyset$. On a alors $\mathcal{P}(E) = \{\emptyset\}$, d'où : $\text{Card }\mathcal{P}(E) = 1 = 2^0$.
• Supposons le résultat vrai au rang $n$. Soit maintenant un ensemble $E$ de cardinal $n+1$. Fixons $a \in E$, et posons $F = E \setminus \{a\}$. Regardons les parties de $E$ ; on distingue :
  • Les parties de $E$ ne contenant pas $a$. Ce sont donc les parties de $F$, et il y en a $2^n$ d'après l'hypothèse de récurrence.
  • Les parties de $E$ contenant $a$. Ce sont des réunions d'une partie de $F$ et du singleton $\{a\}$.
  Il y en a donc autant que de parties de $F$, à savoir $2^n$. Le nombre total de parties de $E$ est donc : $2^n + 2^n = 2^{n+1}$. Le principe de récurrence nous permet alors de conclure.

Preuve. La formule donnant $A_n^p$ provient de la démarche suivante :

1. Parmi les $n$ objets, nous choisissons celui qui prendra la position 1 : Il y a $n$ choix possibles
2. Parmi les $n-1$ objets restants, nous choisissons celui qui prendra la position 2 : Il y a $n-1$ choix possibles
3. Parmi les $n-2$ objets restants, nous choisissons celui qui prendra la position 3 : Il y a $n-2$ choix possibles
4. $\dots$
5. Parmi les $n-(p-1)$ objets, nous choisissons celui qui prendra la position $p$ : Il y a $n-p+1$ choix.

D'où :

Preuve. Le nombre de permutations des éléments de $E$ est le nombre d'arrangements sans répétition de tous les éléments de $E$, c'est-à-dire : $A_n^n = n \times (n-1) \times (n-2) \times \dots \times 2 \times 1$.

Preuve. La formule donnant $C_n^p$ provient de la démarche suivante :

1. Nous écrivons sur des bouts de papier tous les arrangements possibles de $p$ objets pris parmi les $n$ objets : il y en a $A_n^p$
2. Nous regroupons par lots les bouts de papier arrangeant les $p$ mêmes objets.
3. Chaque lot est constitué de permutations de $p$ objets : Chaque lot est donc constitué de $p!$ bouts de papier.
4. Le nombre $C_n^p$ de combinaisons est le nombre de lots obtenus : C'est-à-dire : $C_n^p = \frac{A_n^p}{p!} = \frac{n!}{p!(n-p)!}$

Preuve. 1) On a : $C_n^{n-p} = \frac{n!}{(n-p)!(n-(n-p))!} = \frac{n!}{(n-p)!p!} = C_n^p$, d'où le résultat. L'égalité $C_n^p = C_n^{n-p}$ exprime que dans un ensemble fini à $n$ éléments, il y a autant de parties ayant $p$ éléments que de parties ayant $n – p$ éléments. 2) Soit $E$ un ensemble de cardinal $n + 1$ et $a$ un élément fixé dans $E$. Intéressons-nous aux parties de $E$ de cardinal $p + 1$. Elles sont au nombre $C_{n+1}^{p+1}$. On peut aussi les compter de la manière suivante :

• Les parties de $E \setminus \{a\}$ de cardinal $p + 1$, au nombre de $C_n^{p+1}$.
• Les parties de $E \setminus \{a\}$ de cardinal $p$ auxquelles on rajoute $a$, au nombre de $C_n^p$.

On a donc : $C_n^p + C_n^{p+1} = C_{n+1}^{p+1}$

Preuve. Montrons par récurrence que la formule est vraie pour tout $n \in \mathbb{N}^*$. Initialisation : pour $n = 1$, on a bien : $(a+b)^1 = C_1^0 a^0 b^1 + C_1^1 a^1 b^0$. Hérédité : Supposons que $(a+b)^n = \sum_{k=0}^{n} C_n^k a^k b^{n-k}$ et montrons que $(a+b)^{n+1} = \sum_{k=0}^{n+1} C_{n+1}^k a^k b^{n+1-k}$. On écrit $(a+b)^{n+1} = (a+b)^n(a+b)$, ce qui permet d'utiliser la formule au rang $n$. En développant, il vient alors : Donc : Puis, la formule de Pascal et le fait que $C_{n+1}^0 = C_{n+1}^{n+1} = 1$ donnent : Conclusion : Pour tout $n \in \mathbb{N}^*$, $(a+b)^n = \sum_{k=0}^{n} C_n^k a^k b^{n-k}$.