Nombre de sous-ensembles d'un ensemble fini et cardinal 2^n

Terminale générale Spé · Mathématiques Spé Terminale

À retenir

• Ensemble des parties : P(E) contient tous les sous-ensembles de E. • Formule : Card(P(E)) = 2^n si Card(E) = n. • Parties extrêmes indispensables : et E appartiennent toujours à P(E). • Identité combinatoire : _k=0^n nk = 2^n.

Le cours

L'ensemble des parties d'un ensemble fini P(E) Soit E un ensemble fini à n éléments. L'ensemble de tous les sous-ensembles (ou parties) de E est noté P(E). Il comprend notamment l'ensemble vide et l'ensemble plein E lui-même. Théorème fondamental : Card(P(E)) = 2^n Si Card(E) = n, alors le nombre total de sous-ensembles de E est : Card(P(E)) = 2^n Démonstration par codage binaire Pour définir une partie A E, on examine tour à tour chacun des n éléments de E : • Soit il appartient à A (choix 1). • Soit il n'y appartient pas (choix 0). Définir A équivaut donc à choisir un mot binaire de n bits : il y a 2^n choix. Lien fondamental avec les combinaisons Comme chaque partie a une taille k comprise entre 0 et n, la somme du nombre de sous-ensembles de taille k donne le total : _k=0^n nk = n0 + n1 + + nn = 2^n

Dans ce chapitre

• Arbres de choix, dénombrement intuitif et cardinal d'ensembles de Première
• Réunion, intersection et formule du crible Card(A B) de Première
• Produit cartésien d'ensembles finis et cardinal Card(A B) = n p
• Ensembles disjoints, partitions d'un univers et complémentaire de Première
• Principe multiplicatif pour des choix successifs indépendants
• k-uplets d'un ensemble à n éléments et formule n^k
• Nombre de sous-ensembles d'un ensemble fini et cardinal 2^n
• Permutations d'un ensemble fini à n éléments et factorielle n!
• Dénombrement des anagrammes et permutations d'éléments avec répétition
• Arrangements et tirages ordonnés sans remise A_n^k = n!/(n-k)!
• Combinaisons et tirages non ordonnés sans remise
• Formule du coefficient binomial nk = n!/k!(n-k)!
• Propriétés de symétrie des coefficients binomiaux nk = nn-k
• Relation de récurrence de Pascal nk = n-1k-1 + n-1k
• Construction et lecture du triangle de Pascal
• Formule du binôme de Newton (a+b)^n = _k=0^n nk a^k b^n-k
• Application du binôme au calcul de sommes combinatoires usuelles
• Stratégies de dénombrement par partition en cas disjoints (principe additif)
• Stratégies de dénombrement par passage au complémentaire (événement 'au moins un')
• Dénombrement avec contraintes : fixations d'éléments et ordres partiels
• Arbre de décision et méthodologie pour choisir le modèle de dénombrement adéquat
• Bilan : Synthèse et méthode sur Combinatoire et dénombrement