Prépa, 1re année › Dénombrement › Rédiger une preuve combinatoire
Rédiger une preuve combinatoire : méthode (MPSI)
Méthode
Rédiger une preuve combinatoire
Pour démontrer une identité entre entiers par le dénombrement :
- Choisir un ensemble $X$ dont l'un des membres est visiblement le cardinal (comités, parties, chemins, couples...).
- Le compter d'une seconde façon : par découpage en cas disjoints (on obtient une somme), par choix successifs (un produit), ou par une bijection avec un ensemble connu.
- Conclure : les deux expressions sont égales car elles valent $\operatorname{Card}X$.
On appelle double comptage cette démarche. La rédaction précise toujours l'ensemble compté et justifie que le découpage est disjoint et exhaustif.
Exemple
Comité avec président
Montrons que, pour $1\le k\le n$ : $k\binom{n}{k}=n\binom{n-1}{k-1}$.
Soit $E$ un ensemble de $n$ personnes. On compte l'ensemble $X$ des couples $(A,x)$ où $A\in\mathcal{P}_k(E)$ est un comité et $x\in A$ son président.
- On choisit d'abord le comité ($\binom{n}{k}$ façons), puis le président parmi ses $k$ membres : $\operatorname{Card}X=k\binom{n}{k}$.
- On choisit d'abord le président ($n$ façons), puis les $k-1$ autres membres parmi les $n-1$ personnes restantes : $\operatorname{Card}X=n\binom{n-1}{k-1}$.
D'où l'égalité. Contrôle : $n=5$, $k=2$ donne $2\times10=5\times4$.
Exemple
Somme des $k\binom{n}{k}$
Montrons que, pour $n\ge1$ : $\sum_{k=0}^nk\binom{n}{k}=n2^{n-1}$.
Soit $E$ de cardinal $n$ et $X=\{(A,x)\mid A\subset E,\ x\in A\}$.
- En regroupant selon le cardinal $k$ de $A$ : il y a $\binom{n}{k}$ parties à $k$ éléments, et $k$ choix de $x$ pour chacune, soit $\operatorname{Card}X=\sum_{k=0}^nk\binom{n}{k}$.
- En choisissant d'abord $x$ ($n$ choix), puis $A=\{x\}\cup B$ avec $B\subset E\setminus\{x\}$ quelconque ($2^{n-1}$ choix) : $\operatorname{Card}X=n2^{n-1}$.
Contrôle : $n=3$ donne $0+3+6+3=12=3\times4$.