Dénombrement
Ensembles finis, ensembles dénombrables
Définition d’un ensemble fini, d’un ensemble dénombrable
Soit \( E \) un ensemble. On dit que :
- \( E \) est fini s’il est vide ou s’il existe un entier naturel \( n \) non nul et une application bijective de \( E \) sur \( \left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right] \). Un tel entier \( n \), s’il existe, est unique et appelé cardinal de \( E \), et noté \( \mathrm{Card}(E) \). Par convention, on pose : \( \operatorname{Card}(\varnothing)=0 \).
- \( E \) est dénombrable s’il existe une application bijective de \( E \) sur \( \mathbb{N}^* \).
Cardinal d’un ensemble fini : propriétés
Soient \( E \) et \( F \) deux ensembles.
- Si \( E \) est fini et s’il existe une bijection de \( E \) sur \( F \) et si \( E \) est fini, alors \( F \) est fini et : \( \operatorname{Card}(E)=\operatorname{Card}(F) \).
- Si \( F \) est une partie de \( E \), alors \( F \) est fini et : \( \operatorname{Card}(F) \leqslant \operatorname{Card}(E) \)
- Si \( F \subset E \) et \( \operatorname{Card}(F)=\operatorname{Card}(E) \), alors : \( F=E \)
Cardinal d’une union
Soit \( E \) et \( F \) deux ensembles finis.
- \( E \cup F \) et \( E \cap F \) sont des ensembles finis et : \[ \operatorname{Card}(E \cup F)=\operatorname{Card}(E)+\operatorname{Card}(F)-\operatorname{Card}(E \cap F) \]
- Si \( E \) et \( F \) sont disjoints, alors \( E \cup F \) : \[ \operatorname{Card}(E \cup F)=\operatorname{Card}(E)+\operatorname{Card}(F) \]
- Plus généralement, si \( E_1, \ldots, E_n \) sont \( n \) ensembles deux à deux disjoints, alors \( E_1 \cup \cdots \cup E_n \) est fini et : \[ \operatorname{Card}\left(\bigcup_{i=1}^n E_i\right)=\sum_{i=1}^n \operatorname{Card}\left(E_i\right) \]
Cardinal du complémentaire d’un ensemble
Si \( E \) est un ensemble fini et si \( F \) est une partie de \( E \), alors : \( \operatorname{Card}(\overline{F})=\operatorname{Card}(E)-\operatorname{Card}(F) \).
Lemme des bergers
Soient \( E \) et \( F \) deux ensembles finis \( f \) une application surjective de \( E \) sur \( F \). Si, pour tout élément \( y \) de \( F \), \( f^{-1}(\{y\}) \) est de cardinal \( p \) (\( p \) étant un entier naturel), alors : \( \mathrm{Card}(E)=p \times \operatorname{Card}(F) \).
Cardinal d’un produit
Si \( E \) et \( F \) sont deux ensembles finis, alors : \( \operatorname{Card}(E \times F)=\operatorname{Card}(E) \times \operatorname{Card}(F) \).
Cardinaux des ensembles finis de référence
Listes, applications
Définition
Étant donné un ensemble \( E \), une \( p \)-liste (ou \( p \)-uplet) d’éléments de \( E \) est une application de \( \left[\kern-0.15em\left[ {1,p} \right]\kern-0.15em\right] \) dans \( E \) ; autrement dit une suite \( \left(x_1, \ldots, x_p\right) \) formée d’éléments (non forcément distincts) de \( E \).
Cardinal
- Si \( E \) est un ensemble de cardinal \( n \), il y a \( n^p\) \( p \)-listes d’éléments de \( E \).
- Si \( E \) est un ensemble de cardinal \( p \) et \( F \) est un ensemble de cardinal \( n \), le nombre d’applications de \( E \) dans \( F \) est égal à \( n^p \).
Listes d’éléments distincts, injections
Définition
Étant donné un ensemble \( E \), un arrangement de \( p \) éléments de \( E \) est une \( p \)-liste d’éléments distincts de \( E \) ; autrement dit une suite \( \left(x_1, \ldots, x_p\right) \) formée d’éléments distincts de \( E \), ou encore une application injective de \( \left[\kern-0.15em\left[ {1,p} \right]\kern-0.15em\right] \) dans \( E \).
Cardinal
Si \( E \) est un ensemble de cardinal \( n \), le nombre d’arrangements de \( p \) éléments de \( E \) est: \[ \begin{cases} \displaystyle \frac{n!}{(n-p)!}=n \left( n-1 \right) \cdots(n-p+1) & \text { si } p \leqslant n \\ \hfill 0 \hfill & \text { sinon } \rule[0pt]{0pt}{20pt} \end{cases}\]
Permutations, bijections
Définition
Étant donné un ensemble \( E \) de cardinal \( n \), une permutation de \( E \) est une \( n \)-listes d’éléments distincts de \( E \) ; autrement dit un arrangement de \( n \) éléments de \( E \), ou encore une application bijective de \( E \) sur \( E \).
Cardinal
Si \( E \) est un ensemble de cardinal \( n \), le nombre de permutations de \( E \) est \( n \) !
Combinaisons, parties
Définition
Étant donné un ensemble \( E \) de cardinal \( n \), une combinaison de \( p \) éléments de \( E \) est une partie de \( E \), de cardinal \( p \) ; autrement dit un sous-ensemble \( \left\{x_1, \ldots, x_p\right\} \) formé de \( p \) éléments distincts de \( E \).
Cardinal
Si \( E \) est un ensemble de cardinal \( n \), le nombre de combinaisons de \( p \) éléments de \( E \) est : \[ \binom{n}{p}= \begin{cases} \displaystyle \frac{n!}{p! \left( n-p \right)!} & \text { si } p \leqslant n \\ \hfill 0 \hfill & \text { sinon } \rule[0pt]{0pt}{20pt} \end{cases} \]
Ce résultat est encore vrai si \( p=0 \).
Si \( E \) est un ensemble de cardinal \( n \), alors : \[ \operatorname{Card}(\mathscr{P}(E))=2^{\operatorname{Card}(E)}=2^n \]
Égalités remarquables sur les combinaisons
Si \( n \) et \( p \) sont deux entiers naturels quelconques, alors :
- Si \( 0\leqslant p \leqslant n\) : \( \displaystyle \binom{n}{p}=\binom{n}{n-p} \)
- Si \( n \geqslant 1 \) et \( p \geqslant 1 \), alors : \( \displaystyle \binom{n}{p}=\frac{n}{p}\binom{n-1}{p-1} \)
- \( \displaystyle \sum_{k=0}^n\binom{n}{k}=\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n \)
- Si \( n \) et \( p \) sont deux entiers naturels quelconques, alors (Formule du triangle de Pascal) : \( \displaystyle \binom{n+1}{p+1}=\binom{n}{p+1}+\binom{n}{p} \)