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 p ≥ n.
Si n = 1 alors p ≥ n.
Soit n ∈ N∗ telle que la propriété soit vraie pour tout p ∈ N∗ au rang n. Soit p ∈ N∗ et (x1, … , xn+1) est une liste sans répétition dans ⟦1, p⟧. On distingue deux cas.
- Si p n’est pas dans la liste (x1, … , xn), alors p ≥ 2 et (x1, … , xn) est une liste sans répétition dans ⟦1, p − 1⟧.
- Si p est dans la liste (x1, … , xn), alors xn+1 < p donc la liste obtenue en remplaçant p par xn+1 dans (x1, … , xn) est sans répétition dans ⟦1, p − 1⟧.
Dans les deux cas, on obtient n ≤ p − 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.
On note card(∅) = 0.
Un singleton est un ensemble fini de cardinal 1. Une paire est un ensemble fini de cardinal 2.
On montre ensuite par récurrence sur n ∈ N∗ que toute partie de ⟦1, n⟧ est finie.
Pour n = 1 on a 𝒫(⟦1 ; 1⟧) = {∅, {1}} et ces deux parties sont finies.
Soit n ∈ N∗ 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 :
- si B = ∅ alors A = ∅ ou A = {n + 1} donc A est fini ;
- si n + 1 ∉ A alors A = B qui est fini ;
- sinon il existe une liste bijective (x1, … , xp) sur B d’où (x1, … , xp, n + 1) est une liste bijective sur A.
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⟧ : xi ∈ A}, qui est lui-même décrit par (i1, … , ip). Alors A est décrit par (xi1, … , xip).
Calcul du cardinal
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(E ∖ A).
La réunion A ∪ B est finie avec Card(A ∪ B) = Card(A) + Card(B) − Card(A ∩ B).
- 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).
- Si n = 0 alors E = ∅ donc E × F = ∅ donc la propriété est vérifiée.
- Sinon, il existe une liste bijective (x1, … , xn) sur E et on note pour tout i ∈ ⟦1 ; n⟧, Ai = {xi} × F. Les ensembles Ai sont deux à deux disjoints et de même cardinal que F donc on calcule le cardinal d’une réunion disjointe : Card(E × F) = Card(⋃i=1n Ai) = ∑i=1n Card(Ai) = ∑i=1n Card(F) = n × Card(F) = Card(E) × Card(F).
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 p ∈ N∗, l’ensemble Ep des listes (avec répétitions éventuelles) de p éléments de E est fini avec Card(Ep) = (Card(E))p.
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 :
- les parties de A (et il y en a 2n) ;
- celles qui s’écrivent sous la forme B ∪ {xn+1} où B est une partie de A (et il y en a encore 2n).
Donc card(𝒫(E)) = 2n+1.
Combinaisons
Pour tout n ∈ N∗, 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.
- si p > n alors (p parmi n) = 0 ;
- si 0 ≤ p ≤ n alors (p parmi n) = (n−p parmi n).
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).
| 1 | ||||||
| 1 | 1 | |||||
| 1 | 2 | 1 | ||||
| 1 | 3 | 3 | 1 | |||
| 1 | 4 | 6 | 4 | 1 | ||
| 1 | 5 | 10 | 10 | 5 | 1 | |
| 1 | 6 | 15 | 20 | 15 | 6 | 1 |
- Formule de Pascal
- Pour tout (n, p) ∈ N2, on a (p parmi n) + (p+1 parmi n) = (p+1 parmi n+1).
- celles qui ne contiennent pas (n + 1), et il y en a (p+1 parmi n) ;
- celles qui sont composées d’une combinaison de p éléments dans ⟦1, n⟧ et de l’élément (n + 1), et il y en a (p parmi n).
- Expression des coefficients binomiaux avec la factorielle
- Soit n ∈ N. Pour tout k ∈ N tel que 0 ≤ k ≤ n on a (k parmi n) = (n!)(k! (n − k)!).
La relation est satisfaite pour n = k = 0.
Soit n ∈ N 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! (n − k)!) + (n!)((k − 1)! (n − k + 1)!) = (n! k + n! (n − k + 1))(k! (n − k + 1)!) = ((n + 1)!)(k! (n − k + 1)!).
- Relation diagonale sur les coefficients binomiaux
- Pour tout (n, k) ∈ N2 tel que 1 ≤ k ≤ n, k(k parmi n) = n(k−1 parmi n−1).