Arrangements et permutations
Cours · mathématiques (Première S, Liban), chapitre 16 · Liban, Première, série Sciences · le début du chapitre, la suite sur Adloun
Combien de codes secrets à quatre chiffres peut-on composer sur le clavier d'un coffre-fort ? De combien de manières différentes peut-on attribuer les trois premières places d'une course réunissant douze athlètes, ou encore ranger huit ouvrages distincts sur une étagère ? Ces questions relèvent de l'analyse combinatoire (ou dénombrement), qui a pour objet de compter le nombre d'éléments d'un ensemble fini sans avoir à les énumérer un par un.
Ce chapitre introduit les principes fondamentaux du dénombrement lorsque l'ordre des éléments intervient : la notation factorielle , les arrangements sans répétition (modèle des tirages successifs sans remise), les permutations d'un ensemble fini à éléments, ainsi que les -listes (ou arrangements avec répétition, modèle des tirages successifs avec remise).
Programme : LB-1S · LB-1H
Capacités exigibles
- Utiliser le principe additif (réunion d'ensembles disjoints) et le principe multiplicatif (arbre de choix à plusieurs étapes) pour dénombrer des situations concrètes.
- Manipuler la notation factorielle , utiliser la relation et simplifier des quotients d'expressions comportant des factorielles.
- Reconnaître un arrangement sans répétition de éléments parmi () et calculer leur nombre .
- Dénombrer les permutations d'un ensemble à éléments () ainsi que les anagrammes d'un mot.
- Reconnaître une -liste d'un ensemble à éléments (tirages successifs avec remise) et calculer leur nombre .
- Distinguer, dans un problème de dénombrement où l'ordre compte, les situations avec répétition () des situations sans répétition ().
16.1 Factorielle
16.1.1 Ensemble fini, cardinal et principe additif
Un ensemble est dit fini s'il est vide ou s'il contient un nombre déterminé d'éléments distincts (). Cet entier naturel est appelé le cardinal de l'ensemble et se note . Par convention, le cardinal de l'ensemble vide est nul : .
Soient et deux sous-ensembles finis d'un ensemble .
- Si et sont disjoints (c'est-à-dire si ), alors :
- Plus généralement, si sont sous-ensembles finis deux à deux disjoints ( pour tout ), alors :
- Si et sont deux sous-ensembles finis quelconques (non nécessairement disjoints), alors :
Démonstration
- Lorsque , aucun élément n'appartient simultanément à et à . Énumérer les éléments de revient donc à énumérer tous les éléments de , puis tous ceux de , sans aucun doublon, d'où . La généralisation à ensembles deux à deux disjoints s'obtient de proche en proche.
- Lorsque et ont une intersection non vide, la somme compte deux fois chaque élément appartenant à (une fois dans et une fois dans ). Il faut donc retrancher une fois pour obtenir le nombre exact d'éléments de .
16.1.2 Principe multiplicatif et arbres de dénombrement
Lorsqu'une opération comporte plusieurs choix successifs, on peut représenter toutes les possibilités à l'aide d'un arbre de choix (ou arbre de dénombrement) dont chaque chemin de la racine jusqu'à une feuille correspond à un résultat complet.
Si une procédure se déroule en étapes successives telles que :
- la première étape offre possibilités ;
- pour chacune d'elles, la deuxième étape offre possibilités ;
- pour chaque choix des étapes précédentes, la -ième étape offre possibilités,
alors le nombre total de résultats possibles pour l'ensemble de la procédure est égal au produit :
Un restaurant propose un menu composé d'une entrée choisie parmi (), d'un plat principal choisi parmi () et d'un dessert choisi parmi ().
- Le choix de l'entrée offre possibilités.
- Pour chaque entrée, le choix du plat offre possibilités, soit couples (entrée, plat).
- Pour chaque couple (entrée, plat), le choix du dessert offre possibilités.
D'après le principe multiplicatif, le nombre total de menus complets distincts est :
16.1.3 Notation factorielle
Soit un entier naturel non nul (). On appelle factorielle , et l'on note , le produit de tous les entiers naturels de à :
Par convention, on pose :