Cours : Combinatoire et dénombrement

Combinatoire et dénombrement

Dans tout ce qui suit, sauf indication contraire, $n$ et $k$ sont des entiers naturels.

I Ensembles et $k$-uplets

Principe additif

Soit deux ensembles A et B contenant respectivement $m$ et $n$ éléments et tels que leur intersection soit vide ( $A \cap B=\varnothing$ ), alors leur réunion $A \cup B$ contient $m+n$ éléments. Plus généralement, le nombre d'éléments d'une réunion d'ensembles 2 à 2 disjoints est égal à la somme des nombres d'éléments de chacun des ensembles.

Définition

Le produit cartésien de deux ensembles A et B , noté $A \times B$, est l'ensemble des couples ( $a, b$ ), où $a$ est un élément de $A$, et $b$ un élément de $B$. ( $a, b$ ) s'appelle aussi bien un couple qu'un 2-uplet ou une 2-liste. Le produit cartésien de $n$ ensembles $A_{1}, A_{2}, \ldots, A_{n}$ noté $A_{1} \times A_{2} \times \ldots \times A_{n}$, est l'ensemble des n-uplets (ou n-listes) dont les composantes successives appartiennent respectivement à chacun des ensembles $A_{1}, A_{2}, \ldots, A_{n}$. Cas particulier : le produit cartésien de $k$ fois le même ensemble A se note $A^{k}$. Un k-uplet (ou une k-liste) d'un ensemble A est un élément de $A^{k}$.

Principe multiplicatif

Soit deux ensembles A et B contenant respectivement $m$ et $n$ éléments, alors l'ensemble $A \times B$ contient $m \times n$ couples (ou «2-uplets», ou «2-listes»). Plus généralement, le nombre d'éléments d'un produit cartésien d'ensembles est égal au produit des nombres d'éléments de chacun des ensembles. Cas particulier : le nombre de k-uplets (ou k-listes) d'un ensemble à $n$ éléments est $n^{k}$.

À retenir.

Dans un k-uplet, l'ordre est essentiel, et la répétition est possible.

II Arrangements sans répétition

Définition

Soit $n$ un entier naturel. Le produit des entiers naturels non nuls et inférieurs à $n$ s'appelle factorielle de $\boldsymbol{n}$. On dit aussi factorielle $\boldsymbol{n}$, ou $\boldsymbol{n}$ factorielle. Ce produit se note $\square$ $n$ ! . On obtient alors : $0!=1$ (par convention, un produit vide vaut 1 ). $1!=1,2!=2 \times 1=2,3!=3 \times 2 \times 1=6,4!=4 \times 3 \times 2 \times 1=24$ Et pour les entiers naturels $n$ qui suivent : $n!=n \times(n-1) \times(n-2) \times \ldots \times 2 \times 1$. 1 .

Définition

Un k-uplets d'éléments distincts d'un ensemble à $n$ éléments s'appelle un arrangement sans répétition de $k$ éléments pris parmi $n$. Le nombre d'arrangements sans répétition de $k$ éléments pris parmi $n$ se note $\mathrm{A}_{n}^{k}$.

À retenir

Dans un arrangement sans répétition, l'ordre est essentiel, et la répétition est impossible.

Propriété

On a l'égalité :

$$ \mathrm{A}_{n}^{k}=\frac{n!}{(n-k)!} $$

(pour $\leq k \leq n$ ).

On notera que $A_{n}^{k}=n \times(n-1) \times(n-2) \times \ldots \times(n-k+1)$ (pour $\leq k \leq n$ ). Si $k>n$, alors $\mathrm{A}_{n}^{k}=0$ (il est alors impossible de prendre $k$ éléments distincts parmi $n)$.

Propriété et définition

Une permutation sur un ensemble à $n$ éléments est un arrangement sans répétition de $n$ éléments de l'ensemble (pris parmi $n$ ). Le nombre de permutations d'un ensemble à $n$ éléments est donc égal à $A_{n}^{n}=n$ !

III Combinaisons

Propriété

Le nombre de parties d'un ensemble à $n$ éléments est égal à $2^{n}$.

Définition

Une partie à $k$ éléments d'un ensemble à $n$ éléments s'appelle combinaison de $\boldsymbol{k}$ éléments parmi $n$. Le nombre de combinaisons de $k$ éléments pris parmi $n$ se note $\binom{n}{k}$. Si nous tirons sans remise $k$ objets parmi $n$ objets discernables, et nous les disposons sans tenir compte de l'ordre d'apparition, nous pouvons représenter ces $k$ objets par une partie à $k$ éléments d'un ensemble à $n$ éléments. Ce sont des combinaisons sans répétition de $k$ éléments parmi $n$.

À retenir

Dans une partie (ou une combinaison), l'ordre n'intervient pas, et la répétition est impossible. On obtient directement les coefficients $\binom{n}{k}$ avec les calculatrices : Casio : OPTN PROB n nCr k TI : MATH PRB n Combinaison k

Propriété

On a l'égalité : $\binom{n}{k}=\frac{n!}{(n-k)!k!} \quad($ pour $0 \leq k \leq n)$.

On notera que $\binom{n}{k}=\frac{\mathrm{A}_{n}^{k}}{k!}=\frac{n \times(n-1) \times(n-2) \times \ldots \times(n-k+1)}{k!}($ pour $0 \leq k \leq n)$. Si $k>n$, alors $\binom{n}{k}=0$ (il est alors impossible de prendre $k$ éléments distincts parmi $n$ ).

Propriété

$$ \binom{n}{0}=1 \quad\binom{n}{1}=n \quad(\text { pour } n \geq 1) \quad\binom{n}{2}=\frac{n \times(n-1)}{2}(\text { pour } n \geq 2) $$

Propriété de symétrie

Pour tous les entiers $n$ et $k$ tels que $0 \leq k \leq n$ : $\binom{n}{k}=\binom{n}{n-k}$.

Relation de Pascal

Pour tous les entiers $n$ et $k$ tels que $0<k<n$ : $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$.