Leçon 01 : arbres, tableaux, diagrammes...
Utilisation d’arbres, de tableaux, de diagrammes, pour des exemples simples de dénombrement. Dénombrement des arrangements et des permutations.
Dénombrer, c’est compter les éléments d’un ensemble fini. On supposera donc connu le vocabulaire lié aux ensembles : union, intersection de deux parties d’un ensemble, partition d’un ensemble, cardinal d’un ensemble fini et produit cartésien de deux ensembles.
Les définitions d’application, d’injection, de bijection ne seront pas rappelées.
Notation : le cardinal d’un ensemble E sera noté cardE ; [1,n] désignera l’ensemble {1,2,...,n}.
I. Exemples simples de dénombrement
1. Utilisation de tableaux
a) Tableau récapitulatif
On jette deux dés distincts à quatre faces. On note la somme des points obtenus.
Quelle est la somme qui apparaît le plus souvent et de combien de façons ?
b) Tableau de Caroll
Une population de cent individus est classée suivant deux caractères : le sexe et le fait d’être fumeur ou non.
On sait que 25 hommes sont fumeurs, 20 femmes ne fument pas et qu’il y a en tout 37 fumeurs.
Combien y a-t-il d’hommes et de femmes dans cette population ?
2. Utilisation d’un diagramme de Venn
Dans une classe, on étudie trois langues : l’anglais, l’allemand et l’espagnol.
On suppose que chaque élève étudie au moins une langue et on sait que : 5 élèves étudient les trois langues, 7 élèves étudient l’anglais et l’allemand, 9 élèves étudient
l’allemand et l’espagnol, 8 élèves étudient l’anglais et l’espagnol, 20 élèves étudient l’anglais, 15 élèves étudient l’allemand et 18 élèves étudient l’espagnol.
Combien d’élèves n’étudient que l’anglais ?
Les problèmes de dénombrement résolus à l’aide d’un tableau de Caroll ou d’un diagramme de Venn reposent sur le principe de la somme :
Si E
1, ..., E
n est une partition d’un ensemble fini E, alors cardE = cardE
1 + ... + cardE
n.
3. Utilisation d’arbres
Soit E={1,2,3,4}. Dénombrer tous les nombres formés de trois chiffres distincts de E et
commençant par 1.
Les problèmes de dénombrement résolus à l’aide d’un arbre reposent sur le principe du produit :
Soit p un entier naturel non nul. Si une situation comporte p étapes offrant
respectivement n
1, ..., n
p possibilités (où chaque n
i ne dépend que de l’étape i ) alors le
nombre total d’issues est

.
II. Dénombrement des arrangements et des permutations
Dans toute la suite, E désignera un ensemble fini de cardinal n, n entier naturel non nul.
1. p-listes d’un ensemble fini
Définition :
Soit p un entier naturel non nul. On appelle p-liste d’éléments de E toute suite ordonnée de p éléments de E.
Théorème :
Le cardinal de l’ensemble des p-listes d’éléments de E est np.
Proposition :
Le nombre de parties de E est 2n.
2. Arrangement
Définition :
Soit p un entier naturel non nul tel que p

n.
On appelle arrangement de p éléments de E une p-liste d’éléments de E deux à deux distincts.
Remarques :
Contrairement aux p-listes, il n’y a pas répétition d’un même élément.
Il n’existe aucun arrangement de E à p éléments si p > n.
Théorème :
Le nombre d’arrangements de p éléments de E est fini, il est noté

et on a :
 \times ... \times (n-p+1))
si

et

si

.
Exemple : Calculer le nombre de façons de garer 4 voitures sur un parking comprenant 6 places.
3. Permutation
Définition :
On appelle permutation de E tout arrangement de n éléments de E.
Remarque : Une permutation est liste ordonnée de tous les éléments de E pris une et une seule fois.
Théorème :
Le nombre de permutations de E est
 \times ... \times 1))
, noté

et qui se lit "factorielle n".
Convention : 0! = 1.
Exemple : Calculer le nombre de façons de garer 6 voitures dans un parking comprenant 6 places.
4. Exercice de synthèse
On s’intéresse aux résultats du Loto : on appelle tirage une liste de 6 numéros. Il y en a
On appelle combinaison un ensemble de 6 numéros. Chaque combinaison peut s’obtenir par

tirages. Il y a donc

combinaisons.