Nombre de sous-ensembles (Somme des coefficients binomiaux)

Combinatoire et Dénombrement · niveau 3 (difficile)

Énoncé

Nombre de sous-ensembles (Somme des coefficients binomiaux).

Soit $E$ un ensemble fini à $n$ éléments.

Justifier que le nombre de sous-ensembles de $E$ contenant exactement $k$ éléments ( $0 \leq k \leq n$ ) est $(k n)$ .
En comptant les parties de $E$ de deux façons différentes, déterminer la valeur de la somme :

$S = k = 0 \sum n (k n)$

Corrigé

Choisir un sous-ensemble (ou partie) à $k$ éléments dans un ensemble à $n$ éléments revient à choisir $k$ éléments parmi $n$ sans ordre et sans répétition. C'est exactement le nombre de combinaisons de $k$ éléments parmi $n$ , soit $(k n)$ .

Le nombre total de sous-ensembles de $E$ est la somme du nombre de sous-ensembles à 0 élément, à 1 élément, ..., à $n$ éléments (familles deux à deux disjointes, principe additif) :

$S = k = 0 \sum n (k n)$

Par ailleurs, on a démontré dans le cours (bijection avec les mots de longueur $n$ sur ${0, 1}$ ) qu'un ensemble à $n$ éléments possède exactement $2^{n}$ parties. Les deux comptages portent sur le même ensemble de parties, donc :

$S = 2^{n}$

Remarque : en maths expertes, ce résultat se retrouve aussi par la formule du binôme de Newton $(1 + 1)^{n} = \sum_{k = 0}^{n} (k n)$ .