Pourquoi un ensemble à n éléments possède-t-il 2^n parties ?
Réponse courte
Pour chacun des n éléments, une partie décide indépendamment de le contenir ou non : deux possibilités par élément. Le principe multiplicatif donne donc 2 × … × 2 = 2ⁿ parties.
Comprendre
Deux décisions pour chaque élément
Soit E un ensemble fini de n éléments. Pour fabriquer une partie A de E, on examine chaque élément : il appartient à A ou il n’y appartient pas. Ces deux possibilités sont disponibles pour chacun des n éléments, et les décisions forment un choix complet. Par le principe multiplicatif, on obtient 2ⁿ parties.
Une correspondance qui explique le compte
Fixons un ordre des éléments de E. À une partie, associons une liste de n chiffres : on écrit 1 à la place d’un élément présent et 0 à la place d’un élément absent. Chaque partie donne un seul code, et chaque code décrit une seule partie. Les parties sont donc en bijection avec les listes binaires de longueur n, qui sont au nombre de 2ⁿ.
Vérifier sur de petits ensembles
Si E = {A,B}, les codes 00, 10, 01 et 11 décrivent respectivement ∅, {A}, {B} et {A,B} : il y en a 2² = 4. Pour E = {A,B,C}, il existe 2³ = 8 codes et donc 8 parties. La taille des parties varie ; le total inclut aussi bien l’ensemble vide que E lui-même.
Exemples
- Pour E = {A,B}, les quatre parties sont ∅, {A}, {B}, {A,B} ; 2² = 4.
- Un ensemble à 4 éléments possède 2⁴ = 16 parties, car chaque élément reçoit un choix présence/absence.
- Parmi les parties de {A,B,C}, les codes 000 et 111 représentent ∅ et {A,B,C} : ces deux cas sont compris dans les 8.
Pièges fréquents
- Compter seulement les parties non vides retire le code 00…0 : on obtient 2ⁿ − 1, et non le nombre de toutes les parties.
- Écrire 2n au lieu de 2ⁿ confond une puissance avec un produit : pour n = 4, le compte est 16 et non 8.
Pourquoi ça marche
La bijection par les codes binaires prouve que chaque partie correspond à exactement un choix de n chiffres, sans omission ni double compte.
