Fiche résumé : Combinatoire et dénombrement (Terminale)

Dénombrer, c'est compter les éléments d'un ensemble fini sans les énumérer un par un, à l'aide de quelques modèles bien choisis : k-uplets, permutations, combinaisons. Ces outils servent directement en probabilités, où le calcul d'une probabilité en situation d'équiprobabilité se ramène à compter des issues.

Principe additif : si $A\cap B=\emptyset$, $\mathrm{card}(A\cup B)=\mathrm{card}(A)+\mathrm{card}(B)$. Cas disjoints : on additionne.
Complémentaire : $\mathrm{card}(\overline{A})=\mathrm{card}(E)-\mathrm{card}(A)$. Utile pour « au moins un ».
Principe multiplicatif : $\mathrm{card}(E\times F)=\mathrm{card}(E)\times\mathrm{card}(F)$. Étapes successives : on multiplie.
k-uplets d'un ensemble à $n$ éléments (ordre, répétitions permises) : $n^k$.
Factorielle : $n!=1\times2\times\cdots\times n$, $0!=1$, $n!=n\times(n-1)!$.
k-uplets d'éléments distincts (arrangements ; ordre, sans répétition), $0\leqslant k\leqslant n$ : $n(n-1)\cdots(n-k+1)=\dfrac{n!}{(n-k)!}$.
Permutations d'un ensemble à $n$ éléments : $n!$.
Combinaisons (parties à $k$ éléments ; sans ordre, sans répétition) : $\binom{n}{k}=\dfrac{n!}{k!\,(n-k)!}=\dfrac{n(n-1)\cdots(n-k+1)}{k!}$, et $\binom{n}{k}=0$ si $k>n$.
Valeurs : $\binom{n}{0}=\binom{n}{n}=1$, $\binom{n}{1}=n$, $\binom{n}{2}=\dfrac{n(n-1)}{2}$.
Symétrie : $\binom{n}{n-k}=\binom{n}{k}$ (passage au complémentaire).
Formule de Pascal ($1\leqslant k\leqslant n-1$) : $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ (on distingue les parties contenant ou non un élément fixé).
Triangle de Pascal : lignes $1$ ; $1,1$ ; $1,2,1$ ; $1,3,3,1$ ; $1,4,6,4,1$ ; $1,5,10,10,5,1$ ; $1,6,15,20,15,6,1$.
Nombre de parties d'un ensemble à $n$ éléments : $2^n$ (bijection avec $\{0;1\}^n$).
Somme d'une ligne : $\sum_{k=0}^{n}\binom{n}{k}=2^n$.
Choix du modèle : l'ordre compte-t-il ? Les répétitions sont-elles possibles ? Avec remise : $n^k$ ; sans remise successif : $\frac{n!}{(n-k)!}$ ; simultané : $\binom{n}{k}$.