Rae
Le nombre de sous-ensembles d'un ensemble de 5 éléments est 2^5 = 32. L'un d'entre eux est impropre, donc le nombre de sous-ensembles appropriés est 31.
Le nombre de sous-ensembles d'un ensemble de n éléments est 2^n. L'un d'eux est inapproprié. L'un d'eux est vide.
Considérons un ensemble de 3 éléments, {a, b, c}. Il aura 2^3 = 8 sous-ensembles. Maintenant, envisagez de compter en base 2 (binaire). Voici à quoi ressemble le comptage de 0 à 7 :
000
001
010
011
100
101
110
111
Si vous laissez les chiffres correspondre à a, b, c, et que vous mettez l'élément correspondant de l'ensemble dans le sous-ensemble lorsque le chiffre est 1, vous avez
000 correspond à { }
001 correspond à {c}
010 correspond à {b}
011 correspond à {b, c}
etc. Le dernier sous-ensemble, {a, b, c} est impropre car il contient tous les éléments de l'ensemble d'origine.
Comme vous pouvez le voir, il existe une correspondance de 1 à 1 entre les nombres binaires de 0 à 2^n-1 et les sous-ensembles d'un ensemble de n éléments. Ainsi, il existe 2^n sous-ensembles d'un ensemble de n éléments.