Prépa · MPSI / MP2I

Fiche résumé : Dénombrement (Prépa, 1re année)

Dénombrer, c'est compter les éléments d'un ensemble fini sans les énumérer un par un, en le découpant, en le mettant en bijection avec un ensemble connu ou en le comptant de deux façons. Ces techniques servent en probabilités, en algèbre (formule du binôme, polynômes) et en informatique (complexité, structures de données).

$E$ fini de cardinal $n$ : bijection $\llbracket1,n\rrbracket\to E$. Deux ensembles en bijection ont même cardinal.
$\operatorname{Card}\llbracket a,b\rrbracket=b-a+1$.
$A\subset E$ : $\operatorname{Card}A\le\operatorname{Card}E$, égalité si et seulement si $A=E$.
$\operatorname{Card}f(E)\le\operatorname{Card}E$, égalité si et seulement si $f$ injective. Principe des tiroirs : si $\operatorname{Card}E>\operatorname{Card}F$, aucune injection de $E$ dans $F$.
$E$, $F$ finis de même cardinal, $f:E\to F$ : injective $\Leftrightarrow$ surjective $\Leftrightarrow$ bijective.
Réunion disjointe : on additionne. $\operatorname{Card}(A\cup B)=\operatorname{Card}A+\operatorname{Card}B-\operatorname{Card}(A\cap B)$. $\operatorname{Card}(E\setminus A)=\operatorname{Card}E-\operatorname{Card}A$.
$\operatorname{Card}(E\times F)=\operatorname{Card}E\cdot\operatorname{Card}F$, $\operatorname{Card}(E^p)=(\operatorname{Card}E)^p$.
Lemme des bergers : $f$ surjective avec $k$ antécédents pour chaque image, alors $\operatorname{Card}E=k\operatorname{Card}F$.
$\operatorname{Card}(F^E)=(\operatorname{Card}F)^{\operatorname{Card}E}$ ; $\operatorname{Card}\mathcal{P}(E)=2^n$ (bijection $A\mapsto\mathbf{1}_A$).
$p$-listes d'éléments distincts parmi $n$, injections de $p$ éléments dans $n$ éléments : $\frac{n!}{(n-p)!}$ si $p\le n$, $0$ sinon. Permutations : $\operatorname{Card}\mathfrak{S}_n=n!$.
$\operatorname{Card}\mathcal{P}_k(E)=\binom{n}{k}=\frac{n!}{k!(n-k)!}$ ; et $\frac{n!}{(n-k)!}=k!\binom{n}{k}$.
Symétrie $\binom{n}{k}=\binom{n}{n-k}$ (complémentaire). Pascal $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ (contient $a$ ou non).
Binôme ($ab=ba$) : $(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^kb^{n-k}$ ; $\sum_k\binom{n}{k}=2^n$ ; $\sum_k(-1)^k\binom{n}{k}=0$ pour $n\ge1$.
$k\binom{n}{k}=n\binom{n-1}{k-1}$ ; $\sum_kk\binom{n}{k}=n2^{n-1}$ ; Vandermonde $\sum_k\binom{p}{k}\binom{q}{n-k}=\binom{p+q}{n}$ ; $\sum_k\binom{n}{k}^2=\binom{2n}{n}$.
Modèles : ordre et répétition $n^p$ ; ordre sans répétition $\frac{n!}{(n-p)!}$ ; sans ordre ni répétition $\binom{n}{p}$.
« Au moins un » : passer au complémentaire. Preuve combinatoire : un ensemble, deux comptages, cas disjoints et exhaustifs.