Dénombrement des anagrammes et permutations d'éléments avec répétition

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

À retenir

• Anagrammes sans répétition : n!. • Anagrammes avec répétition : n!/k_1! k_2! k_p!. • On divise par k! pour chaque groupe de k éléments identiques afin de compenser les permutations superflues. • k_1 + k_2 + + k_p = n.

Le cours

Anagrammes avec répétition de lettres Une anagramme d'un mot est une permutation de ses lettres. Si certaines lettres sont répétées, échanger deux lettres identiques ne crée pas un nouveau mot. Il faut donc diviser le nombre total de permutations par les factorielles des multiplicités de chaque lettre répétée. Formule du coefficient multinomial Pour un mot de n lettres contenant k_1 fois une lettre L_1, k_2 fois L_2, ..., k_p fois L_p (avec k_i = n) : N = n!/k_1! k_2! k_p! Exemple classique : MISSISSIPPI Le mot MISSISSIPPI compte 11 lettres : 1 M, 4 I, 4 S, 2 P. Le nombre d'anagrammes distinctes est : N = 11!/1! 4! 4! 2! = 34\,650 Objets indiscernables Ce modèle s'applique dès que l'on aligne des objets indiscernables par groupes : par exemple, ranger en ligne 3 boules rouges et 2 boules bleues donne 5!/3! 2! = 10 alignements de couleurs différents.

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