Dénombrement

Si $A\subset E$ avec $E$ fini, alors $A$ est fini et $|A|\le |E|$, avec égalité si et seulement si $A=E$.

Soient $E,F$ finis de même cardinal et $f:E\to F$. Alors :

$$f\text{ bijective}⟺f\text{ injective}⟺f\text{ surjective}.$$

Version contraposée, dite des tiroirs (ou de Dirichlet) : si l'on range $n+1$ chaussettes dans $n$ tiroirs, un tiroir contient au moins deux chaussettes — toute application d'un ensemble de cardinal $>n$ vers un ensemble de cardinal $n$ est non injective. Simple et redoutable (exercice 5). On notera l'analogie parfaite avec la dimension finie (chapitre 12) : même énoncé, les cardinaux remplaçant les dimensions.

Soient $A,B$ des parties d'un ensemble fini $E$.

• Union disjointe : si $A\cap B=\varnothing$, alors $|A\cup B|=|A|+|B|$ (principe d'addition : on découpe en cas incompatibles) ; plus généralement, pour une partition $E=A_1\bigsqcup \cdots \bigsqcup A_k$ : $|E|=\sum |A_i|$.
• Union quelconque : $|A\cup B|=|A|+|B|-|A\cap B|$ (les éléments de $A\cap B$ étaient comptés deux fois ; la formule du crible générale à $k$ ensembles est hors programme).
• Complémentaire : $\left|\overline{A}\right|=|E|-|A|$ ;   différence : $|A\setminus B|=|A|-|A\cap B|$.
• Produit cartésien : $|A\times B|=|A|\times |B|$ (principe de multiplication : choix successifs indépendants).

Soient $E$ et $F$ finis, $|E|=p$, $|F|=n$.

• Le nombre d'applications de $E$ dans $F$ est $\left|F^E\right|=n^p$ (pour chacun des $p$ éléments de $E$, $n$ choix indépendants d'image).
• Le nombre de parties de $E$ est $\left|\mathcal{P}(E)\right|=2^p$ (pour chaque élément : dedans ou dehors — une partie, c'est une application de $E$ dans $\{0,1\}$).

Soit $E$ de cardinal $n$.

• Le nombre de $p$-listes (ou $p$-uplets) d'éléments distincts de $E$ (l'ordre compte, pas de répétition) est :

$$n(n-1)(n-2)\cdots (n-p+1)=\frac{n!}{(n-p)!}(0\le p\le n)$$

($n$ choix pour le premier, $n-1$ pour le deuxième, etc.).

• Cas $p=n$ : le nombre de permutations de $E$ est $n!$ — on retrouve $|{\mathcal{S}}_n|=n!$ (chapitre 14).
• Le nombre d'applications injectives d'un ensemble de cardinal $p$ dans un ensemble de cardinal $n$ est ce même nombre $\frac{n!}{(n-p)!}$ : une injection, c'est la $p$-liste (sans répétition) de ses valeurs.

Le nombre de parties à $p$ éléments (ou $p$-combinaisons) d'un ensemble de cardinal $n$ est :

$$\left(\genfrac{}{}{0ex}{}{n}{p}\right)=\frac{n!}{p!(n-p)!}=\frac{n(n-1)\cdots (n-p+1)}{p!}.$$

$$\left(\genfrac{}{}{0ex}{}{n}{p}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{p-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{p}\right)(1\le p\le n-1).$$