k-uplets d'un ensemble à n éléments et formule n^k

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

À retenir

• k-uplet d'un ensemble à n éléments : élément de E^k. • Nombre total : n^k. • Modèle type : tirages successifs AVEC remise (l'ordre compte, répétitions permises). • Mots de k lettres sur un alphabet de taille n : n^k mots possibles.

Le cours

Définition d'une liste ordonnée avec répétition (k-uplet) Soit E un ensemble à n éléments. Un k-uplet (ou liste ordonnée de longueur k) d'éléments de E est un élément du produit cartésien E^k = E E E_k fois. Il se note (x_1, x_2, , x_k) où chaque x_i E. Théorème de dénombrement des k-uplets Le nombre de k-uplets d'un ensemble à n éléments est : Card(E^k) = n^k Pour chaque position de 1 à k, il y a indépendamment n choix possibles (les répétitions sont autorisées). Modèle de tirage équivalent Ce dénombrement correspond exactement aux tirages successifs avec remise de k boules parmi n : • L'ordre des tirages compte. • Une même boule peut être tirée plusieurs fois. Mots binaires et octets Avec l'alphabet binaire \0, 1\ (n = 2) : • Le nombre de mots de 8 bits (un octet) est 2^8 = 256. • Le nombre de mots de 16 bits est 2^16 = 65\,536.

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