Comment dénombrer un ensemble fini ?

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)}$. $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!$. On appelle combinaison de $p$ éléments de $E$, ou encore $p$-combinaison de $E$ toute partie à $p$ éléments de $E$. 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}.$$ $(\textrm{card F})^\textrm{card(E)}$ $2^{\textrm{card}(E)}$ $(x_1,\dots,x_p)$ $n^p$ $\frac{n!}{(n-p)!}$ $n!$ $\binom np$ $\binom n{n-p}$ $\binom {n-1}p+\binom{n-1}{p-1}$ $\sum_{k=0}^n \binom nk a^kb^{n-k}$

Un ensemble fini, c’est un ensemble qu’on peut dénombrer à l’aide des entiers naturels \(1,\ldots,n\) pour un certain entier naturel \(n\). Pour compter les éléments d’un ensemble, on utilise la notion de bijection. Une bijection entre deux ensembles \(E\) et \(F\) est une fonction qui transforme les éléments de \(E\) en des éléments de \(F\), de manière très particulière : chaque élément de \(F\) est associé par \(f\) à au plus un élément de \(E\) et tout élément de \(F\) est associé à au moins un élément de \(E\). On dénombre l’ensemble \(E\) en utilisant le même principe de la bijection : on associe un-à-un les éléments de \(E\) aux premiers entiers naturels, jusqu’à avoir associé tous ses éléments. Un ensemble fini, c’est un ensemble dont on peut théoriquement compter les éléments, ce qu’on appelle dénombrer, autrement dit un ensemble qui est en bijection avec un ensemble de la forme \(\{1,2,3,\ldots,n\}\) pour un certain entier naturel \(n\). L’ensemble des nombres de \(1\) à \(n\) est noté \([[1,n]]\). A un ensemble fini \(E\), on peut donc attacher un nombre d’éléments, qui est l’entier naturel \(n\) qu’on obtient en mettant, par définition, \(E\) en bijection avec l’ensemble \([[1,n]]\).