Combinatoire et dénombrement

Principe additif

Soit deux ensembles $\rm A$ et $\rm B$ contenant respectivement $\rm m$ et $n$ éléments et tels que $\rm A\cap B=\emptyset$. 
Alors l’ensemble $\rm A\cup B$ contient $m+n$ éléments.

Principe multiplicatif 

Soit deux ensembles $\rm A$ et $\rm B$ contenant respectivement $m$ et $n$ éléments. 
Alors l’ensemble $A\times B$ contient $m\times n$ éléments.

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

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 $\bf 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$.

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.

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

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=\dfrac{n!}{(n-k)!}$
où $n !=n(n-1)(n-2)\ldots \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)= 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).