Résumé de cours : Dénombrement
Cardinal
- On appelle cardinal d'un ensemble fini $E$ le nombre d'éléments de $E$. On le note $|E|$, $\#E$ ou $\textrm{card}(E)$.
- Soient $E$ et $F$ deux ensembles finis. Alors
- Si $E\subset F$, on a $\textrm{card}(E)\leq \textrm{card}(F)$, avec égalité si et seulement si $E=F$.
- $\textrm{card}(E\times F)=\textrm{card}(E)\times \textrm{card}(F)$.
- $\textrm{card}(E\cup F)=\textrm{card}(E)+\textrm{card}(F)-\textrm{card}(E\cap F)$.
- Le cardinal des applications de $E$ dans $F$ vaut $(\textrm{card F})^\textrm{card(E)}.$
- $\textrm{card}(\mathcal P(E))=2^{\textrm{card}(E)}$.
- Théorème : Une application entre deux ensembles finis de même cardinal est injective si et seulement si elle est surjective si et seulement si elle est bijective.
Listes, permutations, combinaisons
$E$ désigne un ensemble de cardinal $n$.
- On appelle $p$-liste d'éléments de $E$ tout $p$-uplet $(x_1,\dots,x_p)$ d'éléments de $E$. Il y a $n^p$ $p$-listes d'éléments de $E$.
- Le nombre de $p$ listes d'éléments distincts de $E$ vaut $n(n-1)\dots (n-p+1)$. Une telle $p$-liste est parfois appelée un arrangement.
- En particulier, le nombre de permutations de $E$ est égal à $n!$.
- Proposition : Le nombre d'injections d'un ensemble à $p$ éléments dans un ensemble à $n$ éléments vaut $n(n-1)\dots(n-p+1)$.
- On appelle combinaison de $p$ éleménts de $E$, ou encore $p$-combinaison de $E$ toute partie à $p$ éléments de $E$.
- Théorème : Le nombre de combinaisons de $p$ éléments de $E$ (de cardinal $n$) est $\binom np$.