Dénombrement

Définitions
Ensemble fini, cardinal, singleton, paire, permutation, arrangement, combinaison
Notions
liste ordonnée ou non, avec ou sans répétition
Résultats
principe des tiroirs de Dirichlet, cardinal d'une réunion, cardinal du complémentaire, lemme des bergers, formule du crible de Poincaré, cardinal du produit cartésien, d'une puissance, cardinal des ensemble des référence
Compétences
justifier qu'un ensemble est fini ou non, identifier le type des éléments d'un ensemble (liste, partie, application, bijection, arrangement, combinaison), calculer le cardinal d'un ensemble fini

Ensemble fini

Un ensemble E est dit fini s’il est vide ou s’il peut être décrit par une liste (x1, … , xn) exhaustive et sans répétition (on dit alors que la liste est bijective sur E).

Principe des tiroirs de Dirichlet
Soit (n, p) ∈ N. Si (x1, … , xn) est une liste sans répétition dans ⟦1, p, alors pn.
Démonstration
On raisonne par récurrence sur n.

Si n = 1 alors pn.

Soit nN telle que la propriété soit vraie pour tout pN au rang n. Soit pN et (x1, … , xn+1) est une liste sans répétition dans ⟦1, p. On distingue deux cas.

Dans les deux cas, on obtient np − 1 donc n + 1 ≤ p.

Cette propriété, appelée pigeonhole principle en anglais (pour « principe des nichoirs de pigeons »), traduit par contraposée le fait que si l’on répartit un certain nombres d’objets dans un nombre strictement inférieur de tiroirs, il existe au moins un tiroir qui contient deux objets.

Propriété
Si (x1, … , xn) et (y1, … , yp) sont des listes bijectives sur un ensemble E alors n = p.
Démonstration
En notant pour chaque entier k ∈ ⟦1, n le numéro de xk dans la liste (y1, … , yp), on obtient une liste sans répétition dans ⟦1, p donc np. De même en intervertissant les listes on obtient pn. Donc n = p.
Définition
Soit E un ensemble fini non vide. On appelle cardinal de E et on note card(E) ou #E ou encore |E| l’unique entier n pour lequel il existe une liste bijective de n termes sur E.
On note card(∅) = 0.
Un singleton est un ensemble fini de cardinal 1. Une paire est un ensemble fini de cardinal 2.
Propriété
Toute partie d’un ensemble fini est finie.
Démonstration
Le vide est la seule partie de lui-même, et il est fini.
On montre ensuite par récurrence sur nN que toute partie de ⟦1, n est finie.

Pour n = 1 on a 𝒫(⟦1 ; 1⟧) = {∅, {1}} et ces deux parties sont finies.

Soit nN tel que la propriété soit vraie au rang n. Soit A ⊂ ⟦1, n + 1⟧. On pose B = A ∩ ⟦1, n qui est fini par hypothèse de récurrence, et on distingue trois cas :

Enfin, pour toute partie non vide A d’un ensemble E fini et décrit par la liste bijective (x1, … , xn), on pose I = {i ∈ ⟦1, n⟧ : xiA}, qui est lui-même décrit par (i1, … , ip). Alors A est décrit par (xi1, … , xip).

Calcul du cardinal

Propriété
Soient E et F deux ensembles finis disjoints. Leur réunion est un ensemble fini avec card(EF) = card(E) + card(F).
Démonstration
Si E est décrit par la liste bijective (x1, … , xn) et F par (y1, … , yp) alors EF est décrit par (x1, … , xn, y1, … , yp).

Plus généralement, soient E1, … , En sont des ensembles finis deux à deux disjoints. Leur réunion est finie avec Card(i=1n Ei) = i=1n Card(Ei).

Cardinal du complémentaire
Soit A une partie d’un ensemble fini E. On a Card(E) = Card(A) + Card(EA).
Démonstration
D’après la propriété précédente, les ensembles A et EA sont finis or ils sont disjoints donc on trouve la relation par addition des cardinaux.
Propriété
Soient A et B deux parties finies d’un ensemble E.
La réunion AB est finie avec Card(AB) = Card(A) + Card(B) − Card(AB).
Démonstration
On a (AB) ∖ A = B ∖ (AB) avec A et B ∖ (AB) finis et disjoints donc les formules précédentes donnent Card(AB) = Card(A) + Card(B ∖ (AB)) = Card(A) + Card(B) − Card(AB).
Cardinal du produit cartésien
Soient E et F deux ensembles finis. Leur produit cartésien E × F est fini avec Card(E × F) = Card(E) × Card(F).
Démonstration
Soient E et F deux ensembles finis. On note n = Card(E).

Plus généralement, soient E1, … , En des ensembles finis. Leur produit cartésien est fini avec Card(i=1p Ei) = i=1p Card(Ei). En particulier, si E est un ensemble fini non vide, pour tout pN, l’ensemble Ep des listes (avec répétitions éventuelles) de p éléments de E est fini avec Card(Ep) = (Card(E))p.

Propriété
L’ensemble des parties d’un ensemble fini E est un ensemble fini de cardinal 2card(E).
Démonstration
On procède par récurrence sur le cardinal de E.

On a 𝒫(∅) = {∅} qui est bien de cardinal 1 = 20.

Soit n tel que la propriété soit vraie pour tout ensemble fini de cardinal n. Soit E un ensemble fini de cardinal n + 1. On note (x1, … , xn+1) une liste bijective sur E et on pose A = {x1, … , xn}. Les parties de E se répartissent alors comme suit :

Donc card(𝒫(E)) = 2n+1.

Combinaisons

Définition
Soit E un ensemble et pN. On appelle combinaison de p éléments de E toute partie de E de cardinal p.
Pour tout nN, on note (p parmi n) (« p parmi n ») le cardinal de l’ensemble des combinaisons de p éléments dans ⟦1, n.
Par convention, (0 parmi 0) = 1 et pour tout k > 0, (k parmi 0) = 0.

Les parties de ⟦1, n se répartissant en ensembles de combinaisons selon leur cardinal, on obtient la relation k=0n (k parmi n) = 2n.

Propriété
Pour tout nN, (0 parmi n) = (n parmi n) = 1.
Propriété
Pour tout (n, p) ∈ N2,

La formule suivante permet de construire le triangle de Pascal ci-contre, où l’entier n correspond au numéro de ligne (commençant avec 0 en haut) et l’entier p correspond au numéro de case (commençant avec 0 à gauche).

Premières lignes du triangle de Pascal
1
11
121
1331
14641
15101051
1615201561
Formule de Pascal
Pour tout (n, p) ∈ N2, on a (p parmi n) + (p+1 parmi n) = (p+1 parmi n+1).
Démonstration
Les combinaisons de (p + 1) éléments dans ⟦1, n + 1⟧ se répartissent entre deux classes :
Expression des coefficients binomiaux avec la factorielle
Soit nN. Pour tout kN tel que 0 ≤ kn on a (k parmi n) = (n!)/(k! (nk)!).
Démonstration
On procède par récurrence sur n.

La relation est satisfaite pour n = k = 0.

Soit nN tel que la propriété soit vraie au rang n. Pour k = 0 on a (0 parmi n+1) = 1 = ((n + 1)!)/(0! (n + 1)!), et pour tout k ∈ ⟦1, n on a (k parmi n+1) = (k parmi n) + (k−1 parmi n) = (n!)/(k! (nk)!) + (n!)/((k − 1)! (nk + 1)!) = (n! k + n! (nk + 1))/(k! (nk + 1)!) = ((n + 1)!)/(k! (nk + 1)!).

Relation diagonale sur les coefficients binomiaux
Pour tout (n, k) ∈ N2 tel que 1 ≤ kn, k(k parmi n) = n(k−1 parmi n−1).
Démonstration
On utilise la formule avec les factorielles : k(k parmi n) = (n!)/((k − 1)! (nk)!) = n(k−1 parmi n−1).
Pour aller plus loin…
Probabilités