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₁, ..., E_n est une partition d’un ensemble fini E, alors cardE = cardE₁ + ... + 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₁, ..., 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

2. Arrangement

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.

Exemple : Calculer le nombre de façons de garer 4 voitures sur un parking comprenant 6 places.

3. Permutation

Remarque : Une permutation est liste ordonnée de tous les éléments de E pris une et une seule fois.

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.