Dénombrement

Théorème 1 — Soit ${\displaystyle A}$ une partie d'un ensemble fini ${\displaystyle E}$.
Alors A est elle-même finie et ${\displaystyle \mathrm {card} (A)}$ ≤ ${\displaystyle \mathrm {card} (E)}$.
Si en outre ${\displaystyle \mathrm {card} (A)=\mathrm {card} (E)}$, alors ${\displaystyle A=E}$.

Caractérisation des applications injectives — Soit ${\displaystyle E}$ un ensemble fini, ${\displaystyle F}$ un ensemble et ${\displaystyle f}$ une application de ${\displaystyle E}$ dans ${\displaystyle F}$.
On a :

1. ${\displaystyle \mathrm {card} (f(E))}$ ≤ ${\displaystyle \mathrm {card} (E)}$
2. ${\displaystyle f}$ est injective ${\displaystyle \Leftrightarrow }$ ${\displaystyle \mathrm {card} (f(E))=\mathrm {card} (E)}$

Corollaire — Soit ${\displaystyle f}$ une application injective d'un ensemble ${\displaystyle E}$ dans un ensemble ${\displaystyle F}$.
si ${\displaystyle f(E)}$ est fini, alors ${\displaystyle E}$ est fini et ${\displaystyle \mathrm {card} (E)=\mathrm {card} (f(E))}$.

Théorème — Soit E et F deux ensembles finis tels que ${\displaystyle \mathrm {card} (E)=\mathrm {card} (F)}$. Si ${\displaystyle f}$ est une application de ${\displaystyle E}$ dans ${\displaystyle F}$ on a :
${\displaystyle f}$ est injective ${\displaystyle \Leftrightarrow }$ ${\displaystyle f}$ est surjective ${\displaystyle \Leftrightarrow }$ ${\displaystyle f}$ est bijective.

Cardinal de l'union de deux ensembles finis disjoints —  Soient ${\displaystyle E}$ et ${\displaystyle F}$ deux ensembles finis disjoints avec ${\displaystyle \mathrm {card} (E)=k}$ et ${\displaystyle \mathrm {card} (F)=n}$.
Alors on a ${\displaystyle \mathrm {card} (E\cup F)=\mathrm {card} (E)+\mathrm {card} (F)=n+k}$.

Cardinal de l'union de ${\displaystyle n}$ ensembles finis deux à deux disjoints —  Soit ${\displaystyle (E_{i})_{i=1}^{n}}$ une famille de ${\displaystyle n}$ ensembles finis deux à deux disjoints.
Alors on a ${\displaystyle \mathrm {card} (\bigcup _{i=1}^{n}E_{i})=\sum _{i=1}^{n}(\mathrm {card} (E_{i}))}$.

Cardinal du complémentaire —  Soit ${\displaystyle E}$ un ensemble fini, ${\displaystyle A\subset E}$, et ${\displaystyle {\overline {A}}}$ son complémentaire dans ${\displaystyle E}$.
Alors on a ${\displaystyle \mathrm {card} (A)+\mathrm {card({\overline {A}})} =\mathrm {card} (E)}$.

Cardinal de l'union de deux ensembles finis —  Soient ${\displaystyle E}$ et ${\displaystyle F}$ deux ensembles finis.
Alors on a ${\displaystyle \mathrm {card} (E\cup F)=\mathrm {card} (E)+\mathrm {card} (F)-\mathrm {card} (E\cap F)}$.

Cardinal de la réunion disjointe de deux ensembles finis — Soient ${\displaystyle E}$ et ${\displaystyle F}$ deux ensembles finis de cardinaux respectifs ${\displaystyle n}$ et ${\displaystyle k}$.
Alors ${\displaystyle E\sqcup F}$ est finie de cardinal ${\displaystyle \mathrm {card} (E\sqcup F)=\mathrm {card} (E)+\mathrm {card} (F)=n+k}$.

Cardinal de la réunion disjointe de ${\displaystyle n}$ ensembles finis — Soit ${\displaystyle E_{i}}$ une famille d'ensembles finis.
${\displaystyle \mathrm {card} (E_{1}\sqcup E_{2}\sqcup E_{3}\,\dots \,\sqcup E_{n})=\sum _{i=1}^{n}\mathrm {card} (E_{i}).}$

Cardinal du produit cartésien de deux ensembles finis — Soient ${\displaystyle E}$ et ${\displaystyle F}$ deux ensembles finis de cardinaux respectif ${\displaystyle n}$ et ${\displaystyle k}$.
Alors ${\displaystyle E\times F}$ est fini de cardinal ${\displaystyle \mathrm {card} (E\times F)=\mathrm {card} (E)\times \mathrm {card} (F)=nk}$.

Cardinal du produit cartésien d'une suite d'ensembles finis — Soit ${\displaystyle E_{i}}$ une famille d'ensembles finis.
Alors ${\displaystyle \mathrm {card} (E_{1}\times E_{2}\times E_{3}\,\dots \,\times E_{n})=\prod _{i=1}^{n}\mathrm {card} (E_{i}).}$

Cardinal de l'ensemble des parties d'un ensemble fini — Soit ${\displaystyle E}$ un ensemble fini de cardinal ${\displaystyle k}$.
Comme ${\displaystyle {\mathcal {P}}(E)}$ est en correspondance biunivoque avec l'ensemble des applications de ${\displaystyle E}$ dans ${\displaystyle \left\{0,1\right\}}$, alors ${\displaystyle {\mathcal {P}}(E)}$ est un ensemble fini et on a ${\displaystyle \mathrm {card} ({\mathcal {P}}(E))=2^{\mathrm {card} (E)}=2^{k}}$.

Cardinal de l'ensemble des correspondances de ${\displaystyle E}$ dans ${\displaystyle F}$ — Soient ${\displaystyle E}$ et ${\displaystyle F}$ deux ensembles finis.
L'ensemble des correspondances de ${\displaystyle E}$ dans ${\displaystyle F}$, noté habituellement ${\displaystyle \mathrm {Corr} (E,F)}$, s'identifie à ${\displaystyle {\mathcal {P}}(E\times F)}$ donc est fini de cardinal ${\displaystyle \ \mathrm {card} (\mathrm {Corr} (E,F))=2^{\mathrm {card} (E)\times \mathrm {card} (F)}=2^{nk}}$.

Cardinal de l'ensemble des applications de ${\displaystyle E}$ dans ${\displaystyle F}$ — Soient ${\displaystyle E}$ et ${\displaystyle F}$ deux ensembles finis de cardinaux respectifs ${\displaystyle k}$ et ${\displaystyle n}$.
L'ensemble des applications de ${\displaystyle E}$ dans ${\displaystyle F}$, souvent noté ${\displaystyle {\mathcal {F}}(E,F)}$, est fini de cardinal ${\displaystyle \ \mathrm {card} ({\mathcal {F}}(E,F))=\mathrm {card} (F)^{\mathrm {card} (E)}=n^{k}}$ avec la convention 0⁰=1 si ${\displaystyle E}$ et ${\displaystyle F}$ sont tous deux vides.

Cardinal de l'ensemble des surjections de ${\displaystyle E}$ dans ${\displaystyle F}$ — Soient ${\displaystyle E}$ et ${\displaystyle F}$ deux ensembles finis de cardinaux respectifs ${\displaystyle k}$ et ${\displaystyle n}$.
L'ensemble des surjections de ${\displaystyle E}$ dans ${\displaystyle F}$, noté habituellement ${\displaystyle \mathrm {Surj} (E,F)}$, a pour cardinal la somme suivante:
${\displaystyle \ \mathrm {card} (\mathrm {Surj} (E,F))=\sum _{i=0}^{n}(-1)^{i}{\frac {n!}{i!(n-i)!}}(n-i)^{k}}$.
Cette somme est nulle si ${\displaystyle \mathrm {card} (E)<\mathrm {card} (F)}$.