Compter les parties, de deux façons

Le double comptage. Soit $E$ un ensemble à $n$ éléments.

Premier comptage. On range les parties de $E$ selon leur nombre d'éléments $p$ , qui va de $0$ à $n$ . Ces classes sont deux à deux disjointes et les recouvrent toutes ; celle de cardinal $p$ compte $(p n)$ parties, par définition du coefficient binomial. Le nombre total de parties est donc $\sum_{p = 0}^{n} (p n)$ .

Second comptage. Construire une partie, c'est décider pour chacun des $n$ éléments s'il y figure ou non. Cela fait $2$ choix par élément, et deux suites de choix distinctes donnent deux parties distinctes : il y a $2^{n}$ parties.

Les deux comptages portant sur le même ensemble, $\sum_{p = 0}^{n} (p n) = 2^{n}$ .

La somme alternée. Posons $S_{n} = \sum_{p = 0}^{n} (- 1)^{p} (p n)$ et convenons que $(- 1 n - 1) = (n n - 1) = 0$ — il n'y a pas de partie à $- 1$ élément, ni de partie à $n$ éléments dans un ensemble qui n'en a que $n - 1$ . Avec cette convention, la formule de Pascal $(p n) = (p - 1 n - 1) + (p n - 1)$ vaut pour tout $p$ de $0$ à $n$ . Donc

$S_{n} = p = 0 \sum n (- 1)^{p} (p - 1 n - 1) + p = 0 \sum n (- 1)^{p} (p n - 1) .$

Dans la première somme, le changement d'indice $q = p - 1$ donne $\sum_{q = 0}^{n - 1} (- 1)^{q + 1} (q n - 1) = - T$ , où l'on a posé $T = \sum_{q = 0}^{n - 1} (- 1)^{q} (q n - 1)$ . La seconde somme vaut exactement $T$ . Donc $S_{n} = - T + T = 0$ .

Le point à retenir. Compter un même ensemble de deux manières est une démonstration à part entière ; et la formule de Pascal, lue de droite à gauche, fait apparaître un télescopage.

Énoncé

Corrigé

Exercices semblables