Dénombrement

Pages associées
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 existe un entier nN et une bijection entre ⟦1, n et E.
Une partie de N est finie si et seulement si elle est majorée.
On procède d'abord par récurrence pour montrer que toute partie finie est majorée.

Le vide est majoré par 0.

Soit nN tel que toute partie de N en bijection avec ⟦1 ; n soit finie. Soit AN tel qu'il existe une bijection f : ⟦1 ; n + 1⟧ → A. Alors B = f(⟦1 ; n⟧) est majoré par un entier M donc A = B ∪ {f(n + 1)} est majoré par max(M, f(n + 1)).

Réciproquement, on procède par récurrence sur le majorant MN.

Le vide et l'ensemble {0} sont les seules parties de N majorées par 0 et elles sont toutes les deux finies.

Soit MN tel que toute partie majorée par M soit finie. Soit A ⊂ ⟦0 ; M + 1⟧ tel que M + 1 ∈ A. Alors B = A ∖ {M + 1} est une partie finie. Si B = ∅ alors A = {M + 1} qui est fini. S'il existe une bijection f : ⟦1 ; n⟧ → B alors on peut prolonger f en une bijection en posant f(n + 1) = M + 1, donc A est fini aussi.

Dans l'ensemble R la réciproque est fausse : l'ensemble [0 ; 1] est borné alors qu'il contient une infinité de nombres réels.

Toute partie d’un ensemble fini est finie.

Soit B une partie non vide d'un ensemble fini A, qui est donc en bijection avec un intervalle de la forme ⟦1 ; n. Alors B est en bijection avec une partie C ⊂ ⟦1 ; n, qui est donc majorée et finie, donc B est finie également.

Unicité du cardinal

Principe des tiroirs de Dirichlet
Soit (n, p) ∈ (N)2. S’il existe une injection de ⟦1 ; n dans ⟦1 ; p alors on a np.
On raisonne par récurrence, sachant que la propriété est évidente pour n = 1.

Soit nN telle que la propriété soit vraie au rang n.

Soit pN et soit f une application injective de ⟦1, n + 1⟧ dans ⟦1, p. On définit pour tout k ∈ ⟦1, n : si f(k) = p alors g(k) = f(n + 1) ≠ p, sinon g(k) = f(k). Par construction, l’application g est injective et à valeurs dans ⟦1, p − 1⟧ donc par hypothèse de récurrence, on trouve np − 1 donc n + 1 ≤ p.

Donc la propriété est vraie au rang n + 1.

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.

Soit (n, p) ∈ (N)2. S’il existe une bijection entre ⟦1 ; n et ⟦1 ; p alors on a n = p.

La bijection et sa réciproque sont deux injections donc d’après la propriété précédente on trouve np et pn donc n = p.

Pour tout ensemble fini non vide E, il n’existe qu’un seul entier nN pour lequel il existe une bijection entre ⟦1 ; n et E.

Soit E un ensemble fini non vide. Soit (n, p) ∈ (N)2 tel qu’il existe deux bijections f : ⟦1 ; n⟧ → E et g : ⟦1 ; p⟧ → E.

La composée g−1f est une bijection entre ⟦1 ; n et ⟦1 ; p donc on obtient n = p.

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 nN pour lequel il existe une bijection entre ⟦1 ; n et E.

Par convention, on pose Card(∅) = 0.

Un singleton est un ensemble fini de cardinal 1. Une paire est un ensemble fini de cardinal 2.

L’ensemble vide est le seul ensemble fini de cardinal nul.

Deux ensembles finis non vides ont même cardinal si et seulement s’il existe une bijection entre les deux.

Soient E et F deux ensembles finis non vides. On note n = Card(E) et il existe une bijection f : ⟦1 ; n⟧ → E.

Si on a Card(E) = Card(F) alors il existe une bijection g : ⟦1 ; n⟧ → F donc la composée gf−1 est une bijection entre E et F.

Réciproquement, s’il existe une bijection φ entre E et F, alors la composée φf est une bijection entre ⟦1 ; n et F donc on trouve Card(F) = n = Card(E).

Opérations ensemblistes

Soient E et F deux ensembles finis disjoints. Leur réunion est un ensemble fini avec Card(EF) = Card(E) + Card(F).

Si l’un des deux ensembles est vide alors la propriété est évidente.

Si les deux ensembles sont non vides, on note n = Card(E) et p = Card(F) et il existe deux bijections f : ⟦1 ; n⟧ → E et g : ⟦1 ; p⟧ → F. On définit alors l’application h de ⟦1 ; n + p vers EF en posant k ∈ ⟦1 ; n⟧, h(k) = f(k) et k ∈ ⟦n + 1, n + p⟧, h(k) = g(kn).
Cette application est bien bijective.

Cardinal du complémentaire
Soit A une partie d’un ensemble fini E. On a Card(E) = Card(A) + Card(EA).
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.

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

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

Soit f une application entre deux ensembles finis non vides de même cardinal. Dans ce cas, f est injective si et seulement si f est surjective.

On raisonne par double implication, en notant E son ensemble source de f et F son ensemble but.

Supposons f injective. Alors f induit une bijection entre E et f(E) donc Card(f(E)) = Card(E) = Card(F) donc le complémentaire de f(E) est vide dans F donc on trouve f(E) = F donc f est surjective.

Supposons f surjective. On note n = Card(E). Il existe une bijection g : ⟦1 ; n⟧ → E et pour tout yF on note h(y) le plus petit antécédent de y par g ∘ f. Par construction, l’application h est injective entre F et ⟦1, n de même cardinal donc elle est aussi surjective et g ∘ h est bijective et f est sa réciproque donc elle est bijective aussi.

Familles finies

Cardinal d’une réunion disjointe
Soit (Ei)1≤in une famille finie d’ensembles finis deux à deux disjoints. Leur réunion est finie avec Card(i=1n Ei) = i=1n Card(Ei).
Lemme des bergers
Soit E un ensemble. Si cet ensemble est la réunion d’une famille finie (Ai)1≤in d’ensembles finis deux à deux disjoints et tous de même cardinal pN alors E est fini de cardinal n × p.
On démontre la première propriété par récurrence sur nN. La deuxième est un cas particulier.
Formule du crible de Poincaré
Soit (Ai)1≤in une famille finie de parties finies d’un ensemble E. On a Card(i=1n Ai) = S⊂⟦1 ; nS≠∅ (−1)Card(S)−1 Card(iS Ai).
On procède par récurrence sur nN.

Produits et applications

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).
Soit (Ei)1≤in une famille finie d’ensembles finis. Leur produit cartésien est fini avec Card(i=1p Ei) = i=1p Card(Ei).
Cardinal d’une puissance cartésienne
Soit E un ensemble fini non vide et 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.
Soient E et F deux ensembles finis. On note n = Card(E).

Le cas du produit fini se démontre par récurrence sur pN et la dernière propriété en est un cas particulier.

Cardinal de l’ensemble des applications
Soient E et F deux ensembles finis non vides. Alors l’ensemble ℱ(E, F) des applications de E vers F est fini avec Card(ℱ(E, F)) = (Card(F))Card(E).
Cardinal de l’ensemble des parties
Soient E un ensemble fini non vide. Alors l’ensemble 𝒫(E) des parties de E est fini avec Card(𝒫(E)) = 2Card(E).
On définit pour tout A ∈ 𝒫(E) son indicatrice χA : E → {0 ; 1} par χA(x) = 1 si xA et χA(x) = 0 sinon.

Si χA = χB alors pour tout xE on a les équivalences xA ⇔ χA(x) = 1 ⇔ χB(x) = 1 ⇔ xB donc l’application A ↦ χA est injective.

Soit f : E → {0 ; 1}. Alors en posant A = f−1({1}) on trouve f = χA. Donc A ↦ χA est surjective.

Finalement, on trouve une bijection entre 𝒫(E) et ℱ(E, {0 ; 1}) donc Card(𝒫(E)) = 2Card(E).

Permutations et arrangements

Soit E un ensemble fini non vide. Une permutation de E est une bijection de E dans E.
L’ensemble des permutations de E est noté S(E).

L’ensemble des permutations d’un ensemble fini non vide de cardinal n est un ensemble fini de cardinal n! où le point d’exclamation indique la factorielle.

On raisonne par récurrence en notant pour tout nN la proposition plus générale Pn : pour tout couple d’ensembles finis E et F de même cardinal n, l’ensemble Bij(E, F) des bijections entre E et F est fini de cardinal n!

Il existe une seule application entre deux singletons et cette application est bien une bijection donc P1 est vraie.

Soit nN tel que Pn soit vraie. Soient E et F deux ensembles finis de même cardinal n+1.
On fixe un élément xE. La restriction à E ∖ {x} définit une bijection entre Bij(E, F) et la réunion disjointe yF Bij(E ∖ {x}, F ∖ {y}). Donc par hypothèse de récurrence et d’après le lemme des bergers, on obtient bien Card(Bij(E, F)) = Card(F) × (n!) = (n + 1) × n! = (n + 1)!

Soit E un ensemble fini non vide et pN. On appelle arrangement de p éléments de E toute injection de ⟦1 ; p dans E.

Cardinal de l’ensemble des arrangements
Soit E un ensemble fini non vide de cardinal nN et p ∈ ⟦1 ; n. L’ensemble des arrangements de p éléments dans E est fini de cardinal Anp = n!/(np)! = i=0p−1 (ni) = n(n − 1)(n − 2)…(np + 1).
En notant 𝒜p(E) l’ensemble des arrangements de p éléments dans E, on peut définir pour tout α ∈ 𝒜p(E) l’ensemble Pα = {f ∈ Bij(⟦1 ; n⟧, E) : ∀k ∈ ⟦1 ; p⟧, f(k) = α(k)} qui rassemble tous les prolongements possibles de αen une bijection de ⟦1 ; n sur E. Cet ensemble est en bijection avec Bij(⟦p + 1 ; n⟧, Eα(⟦1 ; p⟧)) de cardinal (np)!
L’ensemble {Pα, α ∈ 𝒜p(E)} constitue une partition de Bij(⟦1 ; n⟧, E) donc on obtient d’après le lemme des bergers n! = (np)! × Card(𝒜p(E)).

Combinaisons

Soit pN. Une combinaison de p éléments d’un ensemble E est une partie finie de E de cardinal p.

Soit pN et soit E un ensemble fini de cardinal np. L’ensemble des combinaisons de p éléments de E est fini de cardinal (pn) = n!/p! (np)!

L’ensemble 𝒫p(E) des combinaisons de p éléments de E est inclus dans l’ensemble des parties de E donc il est fini.

Pour toute combinaison C de p éléments de E, l’ensemble des arrangements de p éléments de E dont l’image est C est l’ensemble Bij(⟦1 ; p⟧, C) qui est fini de cardinal p!

Ces ensembles forment une partition de l’ensemble des arrangements de p éléments de E, qui est fini de cardinal Anp.

D’après le lemme des bergers, on trouve donc Anp = p! × Card(𝒫p(E)) donc Card(𝒫p(E)) = Anp/p! = n!/p! (np)!.

Tableau récapitulatif

Cas Opération ensembliste Formule Exemple
Disjonction de cas Réunion Card(AB) = Card(A) + Card(B) − Card(AB) Nombre de cartes qui soient un as ou de trèfle dans un jeu de 32 cartes : Card(A) + Card(♣) − Card(A♣) = 8 + 4 − 1 = 11.
Négation Complémentaire Card(E) = Card(A) + Card(E\A) Nombre d'entiers à trois chiffres : Card([[1 ; 999]]) − Card([[1 ; 99]]) = 999 − 99 = 900.
Couples ou listes d'éléments issus d'ensembles différents Produit cartésien Card(E × F) = Card(E) × Card(F) Nombre de pièces en euros différentes (avec un ensemble P de pays émetteurs et un ensemble V de valeurs) : Card(P) × Card(V) = 15 × 8 = 120.
Listes d'éléments dans un ensemble (avec répétitions éventuelles) Puissance cartésienne Card(Ep) = (Card E)p Nombre de séries possibles lors du lancer de 5 dés standards à 6 faces : 65 = 7776.
Distributions des éléments d'un ensemble dans un autre (avec coïncidences éventuelles) Ensemble d'applications Card(F(E, F)) = (Card(F))Card(E) Nombre de distributions possibles pour les dates de naissance (hors année bissextile) des 38 élèves de la classe : 36538 2 × 1097.
Répartition des éléments d'un ensemble dans un autre (sans coïncidences) Ensemble d'arrangements Anp = n! /(np)! Nombre de tirages possibles de trois cartes d'un jeu de 32 sans remise : A323 = 32 × 31 × 30 = 29760.
Manières d'ordonner un ensemble Ensemble de permutations Card(S(E)) = (Card E)! Nombre de mélanges possibles d'un jeu de 32 cartes : 32! ≈ 2,6 × 1035.
Ensembles d'éléments sans ordre et sans répétition Ensemble de combinaisons (pn) = n!/p! (np)! Nombre de mains de 5 cartes dans un jeu de 32 : (532) = 32 × 31 × 30 × 29 × 28 / 1 × 2 × 3 × 4 × 5 = 201 376.