Compter le nombre de parties d'un ensemble fini

Introduction

• Aujourd'hui, nous allons démontrer que pour un ensemble à n éléments, le nombre de parties est donné par 2^n.
• Cette démonstration peut être exprimée comme la somme des coefficients binomiaux : ( \sum_{p=0}^{n} {n \choose p} ).

Exemple avec un ensemble de 3 éléments

• Considérons un ensemble ( E = { \text{rouge}, \text{bleue}, \text{jaune} } ).
• Parties de l'ensemble :
  • Ensemble vide (1 partie)
  • Parties à un élément : {rouge}, {bleue}, {jaune} (3 parties)
  • Parties à deux éléments : {rouge, bleue}, {rouge, jaune}, {bleue, jaune} (3 parties)
  • Partie à trois éléments : {rouge, bleue, jaune} (1 partie)
• Total : 1 + 3 + 3 + 1 = 8 parties, ce qui correspond à 2^3.

Méthodes de démonstration

1. Dénombrement par nombre d'éléments

• Pour chaque entier naturel ( p ) entre 0 et n, il y a ( {n \choose p} ) parties à p éléments.
• Exemple pour n=3 :
  • 0 éléments : 1 partie ({ })
  • 1 élément : 3 parties
  • 2 éléments : 3 parties
  • 3 éléments : 1 partie
• Conclusion : ( \sum_{p=0}^{n} {n \choose p} = 2^n )

2. Codage binaire

• Numérotation des éléments de l'ensemble : ( x_1, x_2, \ldots, x_n ).
• Chaque partie peut être codée par un nuplet de 0 et 1.
  • 1 pour présence, 0 pour absence.
• Exemples de codage :
  • {rouge, jaune} : (1, 0, 1)
  • {} : (0, 0, 0)
• Chaque partie de l'ensemble correspond à un nuplet unique de 0 et 1, donc il y a 2^n nuplets.

Conclusion

• Il y a autant de parties dans l'ensemble ( E ) que d'éléments dans l'ensemble ( {0, 1}^n ).
• Le nombre d'éléments est connu : 2^n.
• Ainsi, on confirme que le nombre de parties d'un ensemble à n éléments est 2^n.

Remarque finale

• Cette relation peut aussi être démontrée par la formule du binôme de Newton.
• D'autres démonstrations peuvent être trouvées dans une autre présentation de cette série.