Dénombrement avec contraintes : fixations d'éléments et ordres partiels

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

À retenir

• Règle d'or : satisfaire les contraintes en premier (places imposées, choix restreints). • Méthode du bloc pour éléments inséparables : remplacer le groupe par un seul objet, puis multiplier par le nombre de permutations internes au bloc. • Éléments séparés : Total sans contrainte moins méthode du bloc.

Le cours

Gestion des contraintes en dénombrement Les problèmes avancés imposent souvent des contraintes : un élément fixé à une position donnée, deux éléments devant rester côte à côte, ou des éléments devant alterner. La règle fondamentale est de traiter les contraintes en priorité absolue. Méthode du « bloc » (éléments consécutifs) Si deux personnes A et B doivent rester ensemble, on les regroupe dans un super-élément [AB] : 1. On permute les (n-1) entités (le bloc et les autres). 2. On permute l'ordre interne au bloc (2! = 2 choix : AB ou BA). Total = (n-1)! 2!. Fixation de position Si le premier élément est imposé (ex: mot commençant par une voyelle) : 1. On choisit la première place parmi les options permises (p choix). 2. On remplit les places restantes avec les règles standard. Ordre partiel imposé Si p éléments parmi n doivent apparaître dans un ordre fixé (pas forcément côte à côte), on choisit leurs p places (np choix, une seule façon de les y ranger), puis on permute les n - p autres : np (n-p)! = n!/p! Par symétrie, chacun des p! ordres relatifs apparaît dans la même proportion des n! permutations. Éléments qui ne doivent PAS être côte à côte Appliquer le complémentaire : Nombre cherché = Total des permutations - Permutations où ils sont ensemble

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