Parties d'un ensemble fini

Spé. Mathématiques · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel

Définitions et théorèmes

Soit E un ensemble fini. Une partie (ou sous-ensemble) de E est un ensemble dont tous les éléments appartiennent à E. L'ensemble des parties de E, noté \mathcal{P}(E), regroupe toutes ces parties, depuis \varnothing jusqu'à E lui-même.

Théorème (nombre de parties). Si \mathrm{Card}(E) = n, alors \mathrm{Card}\big(\mathcal{P}(E)\big) = 2^n.

Preuve (élément par élément). Construire une partie de E revient à décider, pour chacun des n éléments, s'il est « dedans » ou « dehors ». Cela fait 2 choix par élément, indépendants entre eux, donc 2^n parties par le principe multiplicatif.

Un lien fondamental relie parties et combinaisons : le nombre de parties à exactement k éléments est \binom{n}{k}, et puisque toute partie a une taille comprise entre 0 et n, \sum_{k=0}^{n} \binom{n}{k} = 2^n.

Formules à connaître

  • \mathrm{Card}\big(\mathcal{P}(E)\big) = 2^n.
  • Parties à k éléments : \dbinom{n}{k}.
  • \displaystyle\sum_{k=0}^{n} \dbinom{n}{k} = 2^n.
  • Parties contenant un élément fixé : 2^{n-1}.

Méthodes type bac

Compter par taille. Pour compter les parties d'une taille donnée, on utilise directement les combinaisons \binom{n}{k}. Pour « au plus k éléments », on additionne \binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{k}.

Compter par contrainte d'appartenance. Pour « parties contenant tel élément », on fixe cet élément et on choisit librement pour les autres : 2^{n-1}. Pour « ne contenant pas tel élément », même raisonnement : 2^{n-1}.

Complémentaire. « Au moins … » s'obtient souvent en retranchant les cas « aucun » du total 2^n.

Pièges fréquents

  • Oublier \varnothing et E. Ce sont des parties à part entière, comptées dans 2^n.
  • Confondre « parties » et « éléments ». Un singleton \{a\} est une partie ; l'élément a n'est pas une partie.
  • Confondre 2^n et n^2. Le nombre de parties est 2^n, pas n^2.

Pour l'épreuve

Mémorise : « nombre de parties = 2^n », et « parties à k éléments = \binom{n}{k} ». Ce chapitre fait le pont entre le dénombrement et les combinaisons : la somme \sum \binom{n}{k} = 2^n se retrouve souvent en QCM. Pour les questions « au plus / au moins », additionne les bons termes ou passe au complémentaire.

Concrètement, beaucoup d'exercices déguisent le comptage de parties : choisir un sous-ensemble de produits dans un panier, un ensemble de réponses cochées dans un formulaire, ou une sélection libre d'options. Dès que chaque élément peut être pris ou laissé indépendamment des autres, sans tenir compte d'un ordre, le nombre de configurations est 2^n. Si en revanche la taille du sous-ensemble est fixée, on revient aux combinaisons. Enfin, garde en tête le raisonnement « élément par élément » : il permet de redémontrer rapidement le résultat 2^n et d'adapter le comptage quand certains éléments sont imposés (présents ou absents), ce qui divise le nombre de choix libres et donc l'exposant de 2.