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$ et soit $p\geq 0$.

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)=\frac{n!}{(n-p)!}$, $p\leq n$. Une telle $p$-liste est 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$ éléments de $E$, ou encore $p$-combinaison de $E$ toute partie à $p$ éléments de $E$.

Théorème : Soit $p\in\{0,\dots,n\}$. Le nombre de combinaisons de $p$ éléments de $E$ (de cardinal $n$) est $\binom np$.

Les coefficients binomiaux vérifient la formule de symétrie suivante : si $0\leq p\leq n$, alors $$\binom np=\binom n{n-p}.$$

Formule du triangle de Pascal : si $1\leq p\leq n$, alors $$\binom np=\binom {n-1}p+\binom{n-1}{p-1}.$$

Formule du binôme de Newton : si $a$ et $b$ sont deux nombres réels et $n$ est un entier naturel, alors $$(a+b)^n=\sum_{k=0}^n \binom nk a^kb^{n-k}.$$

Dénombrement