Combinatoire et dénombrement · Cours

Choisir ce que l’on compte

Le cardinal d’un ensemble fini $A$, noté $\operatorname{Card}(A)$, est son nombre d’éléments. Un $k$-uplet est une liste ordonnée de $k$ éléments : changer l’ordre peut changer la liste. Dans une partie, l’ordre ne compte pas.

Pour compter, préciser si l’ordre compte, si les répétitions sont autorisées et quelles contraintes s’appliquent.

\operatorname{Card}(A\cup B)=\operatorname{Card}(A)+\operatorname{Card}(B)\quad\text{si }A\cap B=\varnothing.

Le principe additif s’étend aux cas deux à deux disjoints. Le produit cartésien $A\times B$ est l’ensemble des couples $(a,b)$ avec $a\in A$ et $b\in B$.

\operatorname{Card}(A\times B)=\operatorname{Card}(A)\operatorname{Card}(B).

Voir un exemple — Énumérer les six couples d’un produit cartésien

Lister des couples dans un tableau

On considère $A=\{L,M\}$ et $B=\{2,5,8\}$. Un couple est une liste ordonnée de deux éléments. Ici, la première place contient $L$ ou $M$, et la seconde $2$, $5$ ou $8$. Chaque case du tableau donne un couple ; par exemple $(L,5)$.

Il y a deux choix pour la première coordonnée et trois pour la seconde. Les six couples possibles sont tous présents dans le tableau.

$A\backslash B$	$2$	$5$	$8$
$L$	$(L,2)$	$(L,5)$	$(L,8)$
$M$	$(M,2)$	$(M,5)$	$(M,8)$

Listes, permutations et parties

Soit un ensemble de $n$ éléments. Une liste de longueur $k$ avec répétition offre $n$ choix à chaque place : il y en a $n^k$.

n!=1\times2\times\cdots\times n\quad(n\geq1),\qquad 0!=1.

Pour $0\leq k\leq n$, le nombre de listes de $k$ éléments distincts est :

n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}.

Une permutation utilise les $n$ éléments une fois chacun : il y en a $n!$. Une partie se code en choisissant, pour chaque élément, de le prendre ou non ; un ensemble de $n$ éléments possède donc $2^n$ parties. Les listes de longueur zéro et la partie vide comptent chacune pour un objet.

Comprendre pourquoi — Pourquoi multiplier les choix avec répétition

Construisons une liste en remplissant ses $k$ positions l'une après l'autre.

Chacune des $k$ positions peut être occupée par l'un des $n$ éléments de $A$. Le nombre de choix ne diminue pas, car on peut réutiliser un élément. Le principe multiplicatif donne donc $n\times\cdots\times n=n^k$, avec $k$ facteurs.

Combinaisons et coefficients binomiaux

Une combinaison de $k$ éléments parmi $n$ est une partie de $k$ éléments, sans ordre ni répétition. Pour $0\leq k\leq n$ :

\binom nk=\frac{n!}{k!(n-k)!},\qquad \binom n0=\binom nn=1,\qquad \binom n1=n,\qquad \binom n2=\frac{n(n-1)}2\ (n\geq2).

\binom nk=\binom n{n-k},\qquad \binom{n+1}k=\binom n{k-1}+\binom nk\quad(1\leq k\leq n).

Le triangle de Pascal commence par $1$. Chaque ligne commence et finit par $1$ ; chaque terme intérieur est la somme des deux termes au-dessus.

\sum_{k=0}^n\binom nk=2^n.

Exemple : choisir trois robots parmi huit, sans leur attribuer de rôles, donne $\binom83=56$ choix ; une liste ordonnée de trois robots distincts donnerait $8\times7\times6=336$ choix.

Comprendre pourquoi — La relation de Pascal par deux catégories disjointes

Pour $n\ge1$ et $1\le k\le n$, fixons un élément dans un ensemble de $n+1$ éléments. Les parties de taille $k$ qui le contiennent sont au nombre de $\binom n{k-1}$ ; les autres de $\binom nk$. Ces catégories disjointes couvrent tous les cas : leur somme vaut $\binom{n+1}k$.