Dénombrement

Définition : Un ensemble $\rm E$ est fini s’il est vide ou s’il existe $n\in \mathbb N^*$, tel que l’ensemble $[|1; n|]$ soit en bijection avec $\rm E$.

Si $\rm E$ est fini non vide, $n$ est appelé le cardinal de $\rm E$, c’est-à-dire le nombre d’éléments de $\rm E$.

On note $n= |\rm E|=card(E)$.

Par convention, l’ensemble vide a pour cardinal $0$.

Théorème : Soit $\rm A$ une partie de $\rm E$, qui est un ensemble fini.

Alors $\rm A$ est une partie finie et : $\rm |A|\leq|E|$.

$\rm |A|=|E|$ si et seulement si $\rm A=E$.

Théorème : Une application entre deux ensembles finis de même cardinal est bijective si et seulement si elle est injective, si et seulement si elle est surjective.

Opérations sur les cardinaux : soient $\rm A$ et $\rm B$ deux ensembles :

• $\rm |A\cup B|=|A|+|B|-|A\cap B|$.
• Si $\rm A$ et $\rm B$ sont disjoints, $\rm |A\cup B|=|A|+|B|$.
• $\rm |A\times B|=|A|\times |B|$

Remarque : ces principes peuvent se généraliser à un nombre fini quelconque d’ensembles (avec des ensembles deux à deux disjoints pour le principe additif).

• Si $\rm A\subset B$, $\rm |\bar{A}|=|B|-|A|$

Théorème : Soit $\rm E$ un ensemble à $n$ éléments.

Alors, l'ensemble $\rm P(E)$ des parties de $\rm E$ est fini et possède $2^n$ éléments.

Exemple : Le nombre de mots de longueur $n$ sur un alphabet à $2$ éléments est $2^n$.

Théorème : Soient $\rm E$ et $\rm F$ deux ensembles finis.

Le cardinal de l’ensemble des applications de $\rm E$ vers $\rm F$ est égal à : $\rm |F|^{|E|}$.

Définition : Une $\bf k$-liste (ou $\bf k$-uplet) d'éléments d'un ensemble $\rm E$ est une liste ordonnée de $k$ éléments de $\rm E$ non nécessairement distincts. C'est un élément du produit cartésien $\mathrm E^k= \rm E\times E\times \ldots E$ ($k$ termes).

Proposition : Le nombre de $k$-listes d’un ensemble à $n$ éléments est le nombre de possibilités de choisir $k$ éléments, dans un ensemble à $n$ éléments, avec prise en compte de l’ordre des éléments : $n^k$.

Définition : Un arrangement de $k$ éléments de $\rm E$ est une $k$-liste d'éléments distincts de $\rm E$.

Proposition : Soit $\rm E$ un ensemble à $n$ éléments.

Il y a $\mathrm A_n^k$ arrangements de $k$ éléments parmi $n$ :

$\mathrm A_n^k=\displaystyle\frac{n!}{(n-k)!}$

où $n!=n(n-1)(n-2)…\times 1$ est appelé factorielle $n$.

Définition : Soit $\rm E$ un ensemble à $n$ éléments.

Un arrangement de $n$ éléments parmi $n$ s'appelle une permutation de $\rm E$.

Remarque : il y a $n!$ permutations de $\rm E$.

Définition : Soit $\rm E$ un ensemble à $n$ éléments

Une combinaison de $p$ éléments de $\rm E$ est une collection non ordonnée de $p$ éléments distincts de $\rm E$, c’est-à-dire toute partie de $\rm E$ à $p$ éléments.

Attention : On ne doit pas confondre arrangement et combinaison. Dans un arrangement l’ordre des éléments intervient, contrairement à une combinaison.

Proposition : Le nombre de combinaisons de $p$ éléments parmi $n$ est:

$\left(\begin{array}{l} n\\p\end{array}\right)= \mathrm C_n^p=\displaystyle\frac{n!}{p!(n-p)!}$

Remarque : $\left(\begin{array}{l} n\\p\end{array}\right)$ est appelé coefficient binomial.

Propriétés :

$\left(\begin{array}{l} n\\0\end{array}\right)=1$

$\left(\begin{array}{l} n\\1\end{array}\right)=n$

$\left(\begin{array}{l} n\\n\end{array}\right)=1$

$\left(\begin{array}{l} n\\p\end{array}\right)= \left(\begin{array}{l} \quad n\\n-p\end{array}\right)$ (formule de symétrie)

$\left(\begin{array}{l} n\\p\end{array}\right)= \left(\begin{array}{l} n-1\\\quad p\end{array}\right)+ \left(\begin{array}{l} n-1\\p-1\end{array}\right)$ (triangle de Pascal).