Adloun

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

16.1 Factorielle

16.1.1 Ensemble fini, cardinal et principe additif

Définition 16.1Cardinal d'un ensemble fini

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 : .

Proposition 16.2Principe additif

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.

Proposition 16.3Principe multiplicatif

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 :

Exemple 16.4Application directe du principe multiplicatif

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

Définition 16.5Factorielle d'un entier naturel

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 :

La suite du cours · Exercices corrigés