# Introduction aux mathématiques/Rudiments de combinatoire

On dit que deux ensembles $X$ et $Y$ sont équipotents, ou qu'ils ont même cardinal, s'il existe une bijection de $X$ dans $Y$. On note alors : $X\sim Y$.
Cette « relation binaire » (qui n'en n'est pas une car la classe de tous les ensembles n'est pas un ensemble) est clairement une « relation » d'équivalence.

## Ensembles finis

Pour tout $n\in \mathbb {N}$, on pose $\mathbb {N} _{n}=\{0,1,\dots ,n-1\}$, en particulier $\mathbb {N} _{0}=\varnothing$.
Soit $p,n\in \mathbb {N}$. S'il existe une injection de $\mathbb {N} _{p}$ dans $\mathbb {N} _{n}$, alors $p\leq n$.
On procède par récurrence sur n. Si n = 0, le résultat se déduit du fait qu'il n'existe aucune application d'un ensemble non vide dans l'ensemble vide. On suppose le résultat pour N$_n$. Soit j une injection de N$_p$ dans N$_{n+1}$. On doit montrer que p ≤ n + 1, ce qui est immédiat si p = 0. Supposons donc p ≠ 0. Si j(p – 1) = n, j définit par restriction une injection de N$_{p–1}$ dans N$_n$ donc, par hypothèse de récurrence, p – 1 ≤ n. Sinon, on se ramène à ce cas en composant j avec la transposition de N$_{n+1}$ qui échange n et j(p – 1).
On en déduit immédiatement :
Soit $p,n\in \mathbb {N}$. $\mathbb {N} _{p}\sim \mathbb {N} _{n}$ (si et) seulement si $p=n$.
Ceci permet de définir
On dit d'un ensemble $E$ qu’il est fini s'il existe $n\in \mathbb {N}$ tel que $E$ soit en bijection avec $\mathbb {N} _{n}$.
Dans ce cas cet entier est unique, et appelé cardinal de $E$, noté $\#E$, ou $\operatorname {card} (E)$, ou $|E|$.
Ainsi dans « l’ensemble » des ensembles finis, le cardinal caractérise les « classes d'équivalence » de la « relation » $\sim$.

## Propriétés des ensembles finis
### Parties d'un ensemble fini

Soient E un ensemble fini et A une partie de E, alors A est fini et card(A) ≤ card(E).
Il suffit (à bijection près) de démontrer que toute partie de N$_n$ est finie (son cardinal sera nécessairement inférieur ou égal à n, d'après la proposition ci-dessus). On procède par récurrence sur n. Si n = 0, c'est-à-dire si N$_n$ = ∅, le résultat est immédiat. On suppose le résultat pour N$_n$. Soient F une partie de N$_{n+1}$ et G = F\{n}. Par hypothèse de récurrence, G est fini. Si n ∉ F alors F = G. Si n ∈ F, soit q le cardinal de G. On complète une bijection de G dans N$_q$ en une bijection de F = G∪{n} dans N$_{q+1}$ en associant à n l'entier q.
Ce lemme sera complété par le corollaire 1 ci-dessous.

### Union d'ensembles finis

* Si E et F sont deux ensembles finis disjoints alors E∪F est fini et card(E∪F) = card(E) + card(F).
* Si E est un ensemble fini et F un ensemble quelconque, alors les ensembles E∩F et E\F sont finis et card(E) = card (E ∩ F) + card (E\F).
* On note n = card(E) et p = card(F) et l'on fixe $f:E\to \mathbb {N} _{n}$ et $g:F\to \mathbb {N} _{p}$ deux bijections. On définit $\phi :E\cup F\to \mathbb {N} _{n+p},\,x\mapsto {\begin{cases}f(x)&{\text{si }}x\in E\\g(x)+n&{\text{si }}x\in F,\end{cases}}$ bien définie car $E\cap F=\varnothing$ ; on définit également $\psi :\mathbb {N} _{n+p}\to E\cup F,\,k\mapsto {\begin{cases}f^{-1}(k)&{\text{si }}k\leq n\\g^{-1}(k-n)&{\text{si }}k>n.\end{cases}}$ On vérifie qu’il s'agit de deux bijections réciproques l'une de l'autre, ce qui donne bien card(E∪F) = n + p = card(E) + card(F).
* Si E est fini alors E∩F et E\F aussi (voir supra). Comme ils sont disjoints, on peut leur appliquer ce qui précède. On conclut en utilisant que leur réunion est E.
Soient E un ensemble fini et A une partie de E. Si card(A) = card(E), alors A = E.
Soit B = E\A. D'après le lemme, B est fini et card(E) = card(A) + card(B), donc si card(A) = card(E), alors card(B) = 0 c'est-à-dire B = ∅, d'où A = E.
Remarque : ce résultat ne s'étend pas aux ensembles infinis : $\mathbb {N}$ et $\mathbb {N} ^{*}$ sont équipotents bien que l'inclusion soit stricte.
Soient $n\in \mathbb {N}$ et $F_{1},F_{2},\dots ,F_{n}$ des ensembles finis deux à deux disjoints.
Alors l'ensemble $\bigsqcup _{i=1}^{n}F_{i}$ est fini, de cardinal $\sum _{i=1}^{n}\left|F_{i}\right|$.
Par récurrence, grâce au point 1 du lemme (avec la convention, pour le cas n = 0, qu'une union indexée par ∅ est vide et qu'une somme indexée par ∅ est nulle).
Soient $E$ et $F$ deux ensembles finis. Alors $E\times F$ est fini, de cardinal $\left|E\right|\times \left|F\right|$.
On écrit la partition $E\times F=\bigsqcup _{x\in E}\{x\}\times F$, et on justifie que $\left|\{x\}\times F\right|=\left|F\right|$ par la bijection $\{x\}\times F\rightarrow F,(x,y)\mapsto y$. Il suffit alors d'appliquer le corollaire 2.
Une variante plus directe consiste à supposer (sans perte de généralité) que $E=\mathbb {N} _{m}$ et $F=\mathbb {N} _{n}$ et à vérifier que l'application $\mathbb {N} _{m}\times \mathbb {N} _{n}\to \mathbb {N} _{mn},\,(x,y)\mapsto x+my$ est bijective.
Ce résultat s'étend à un produit fini ; en particulier, on a $\left|F^{m}\right|=\left|F\right|^{m}$.
Si E et F sont deux ensembles finis alors E∪F est fini et card(E∪F) = card(E) + card(F) – card(E∩F).
On applique le lemme à E∪F = (E\F)∪(F\E)∪(F∩E) , E = (E\F)∪(E∩F) et F = (F\E)∪(E∩F).
Soient $n\in \mathbb {N}$ et $F_{1},F_{2},\dots ,F_{n}$ des ensembles finis.
Alors l'ensemble $\bigcup _{i=1}^{n}F_{i}$ est fini, de cardinal $\sum _{\varnothing \neq I\subset \mathbb {N} _{n}}(-1)^{\left|I\right|-1}\left|\cap _{i\in I}F_{i}\right|$.
On peut déduire cette généralisation du corollaire 3 (par récurrence), ou la démontrer directement : voir Formule du crible.

### Applications entre ensembles finis

Soit $E$ un ensemble fini.
* Si $g:F\to E$ est une injection, alors $F$ est fini et $\left|F\right|\leq \left|E\right|$, avec égalité si et seulement si $g$ est bijective.
* Si $f:E\rightarrow F$ est une surjection, alors $F$ est fini et $\left|F\right|\leq \left|E\right|$, avec égalité si et seulement si $f$ est bijective.
* Si $g:F\to E$ est une injection, alors son image est d'une part équipotente à $F$ et d'autre part (voir supra) finie, de cardinal inférieur ou égal à celui de $E$, avec égalité si et seulement si $g$ est surjective.
* Sans perte de généralité, on peut supposer que $E=\mathbb {N} _{n}$. Si $f:\mathbb {N} _{n}\rightarrow F$ est une surjection, l'application $g:F\to E,y\mapsto \min \left(f^{-1}(y)\right)$ est injective, puisque $f\circ g=\operatorname {Id} _{F}$. D'après le point précédent, $F$ est donc fini, de cardinal inférieur ou égal à celui de $E$, avec égalité si et seulement si $g$ est bijective, c'est-à-dire (puisque $f\circ g=\operatorname {Id} _{F}$) si et seulement si $f$ est bijective.
Soient $E$, $F$ deux ensembles finis de même cardinal et $f:E\rightarrow F$.
Alors, $f$ injective $\Leftrightarrow \;f$ surjective $\Leftrightarrow \;f$ bijective.

## Quelques cardinaux usuels

Soient $E$ et $F$ deux ensembles finis. Alors, l'ensemble $F^{E}$ des applications de $E$ dans $F$ est fini, de cardinal $\left|F\right|^{\left|E\right|}$.
Si $E$ est vide, il n'y a en effet qu'une application partant du vide et la convention $n^{0}=1$ valide la formule.
Si $F$ est vide sans que $E$ le soit, il n'existe aucune application de $E$ dans $F$, ce qui donne bien $0=0$.
Traitons le cas plus significatif de deux ensembles non vides et supposons sans perte de généralité que $E=\mathbb {N} _{m}$. L'application $F^{\mathbb {N} ^{m}}\to F^{m},\,f\mapsto (f(i-1))_{1\leq i\leq m}$ est une bijection, donc la proposition se déduit du corollaire vu précédemment sur le cardinal d'un produit de deux ensembles finis, via sa conséquence sur le cardinal d'une puissance finie d'ensemble fini.

### Variantes

   * Une variante s'appuie sur la définition par récurrence de la fonction exponentielle sur les entiers naturels : $n^{0}=1$ et $n^{m+1}=n^{m}\times n$. On procède donc par récurrence sur $\left|E\right|$, en utilisant, pour l'hérédité, que pour $e\in E$ fixé et $G=E\setminus \{e\}$, l'application $F^{E}\to F^{G}\times F,\,f\mapsto \left(f_{|G},f(e)\right)$ est bijective.
   * Si $\left|F\right|=n\geq 2$, une méthode plus directe, en supposant sans perte de généralité que $E=\mathbb {N} _{m}$ et $F=\mathbb {N} _{n}$, consiste à remarquer que l'application $\mathbb {N} _{n}^{\mathbb {N} _{m}}\to \mathbb {N} _{n^{m}},\,f\mapsto \sum _{i=0}^{m-1}n^{i}f(i)$ est bijective (la bijection réciproque associe, à tout entier de $\mathbb {N} _{n^{m}}$, sa représentation en base $n$).
Remarque : cela « justifie » un peu la notation $F^{E}$.
Si $E$ est fini alors l'ensemble ${\mathcal {P}}(E)$ des parties de $E$ est fini, de cardinal $2^{\left|E\right|}$.
L’application $\chi :{\mathcal {P}}(E)\rightarrow \{0,1\}^{E},\,A\mapsto \chi _{A}$, où $\chi _{A}$ désigne la fonction indicatrice de $A$, est bijective : cf. Application (mathématiques)/Application caractéristique.
Signalons enfin qu'à l'aide du corollaire 2 ci-dessus appliqué à des partitions en fibres (chap. 3), on démontre successivement les deux propriétés suivantes (cf. Combinatoire, chapitres « Arrangements sans répétition » et « Combinaisons sans répétition ») :
* Le nombre d'injections d'un ensemble à k éléments dans un ensemble à n éléments est :
    $A_{n}^{k}={\begin{cases}{\frac {n!}{(n-k)!}}&{\text{ si }}0\leq k\leq n\\0&{\text{ sinon.}}\end{cases}}$
* Le nombre de parties à k éléments d'un ensemble à n éléments est :
    ${\binom {n}{k}}={\begin{cases}{\frac {n!}{k!\,(n-k)!}}&{\text{ si }}0\leq k\leq n\\0&{\text{ sinon.}}\end{cases}}$

## Les infinis
### Généralités

L'ensemble des entiers naturels nous a servi à classer les ensembles finis suivant leur cardinal. Mais par exemple $\mathbb {N}$ lui-même n’est pas fini, c’est un exemple d'ensemble infini. On souhaiterait quand même les classer. L’idée intuitive est que si l’on peut injecter un ensemble dans un autre, alors le premier est plus petit.
Cette « relation binaire » est réflexive (l'identité est injective) et transitive (la composée d'injections l'est aussi). C'est un « pré-ordre » et le théorème de Cantor-Bernstein montre que la « relation » d'équivalence associée est exactement l'équipotence.
La seconde question qui vient est : tous les ensembles infinis sont-ils équipotents entre eux ? La proposition suivante y répond par la négative, mais laisse entrevoir une théorie intéressante traitant des cardinaux infinis.
Soit $E$ un ensemble. Alors il n'existe pas de surjection, et a fortiori pas de bijection, de $E$ sur ${\mathcal {P}}(E)$.
Fixons une application $f:E\to {\mathcal {P}}(E)$. Pour montrer qu'elle n'est pas surjective, on s'intéresse à la partie $A$ de $E$ définie par $A:=\{x\in E\mid x\notin f(x)\}$ et l'on constate que pour tout $a\in E$, $f(a)\neq A$, puisque $a\in A\Leftrightarrow a\notin f(a)$.
Tout ensemble contenant un ensemble dénombrable est infini (pour plus de détails, voir l'exercice 1-3). En supposant une version faible de l'axiome du choix, la réciproque est vraie :
Si un ensemble $E$ est infini, il existe une injection de $\mathbb {N}$ dans $E$.
À l'aide de l'axiome du choix dépendant, on peut construire par récurrence une suite d'injections $\phi _{n}:\mathbb {N} _{n}\rightarrow E$, de telle façon que $\phi _{n+1}$ prolonge $\phi _{n}$. On pose alors $\phi :\mathbb {N} \rightarrow E,n\mapsto \phi _{n+1}(n)$, qui est bien injective : si $m<n$ alors $\phi (m)\neq \phi (n)$ car $\phi _{m+1}(m)=\phi _{n+1}(m)\neq \phi _{n+1}(n)$.
Pour des preuves n'utilisant que l'axiome du choix dénombrable, voir les articles de Wikipédia « Ensemble infini » et « Axiome du choix dénombrable ».
En quelque sorte, $\mathbb {N}$ est le plus petit ensemble infini. On s'intéresse plus particulièrement à sa classe d'équipotence dans la section suivante.

### Ensembles dénombrables

Un ensemble est dit dénombrable s'il est équipotent à $\mathbb {N}$. Il est dit au plus dénombrable s'il est fini ou dénombrable.
Outre l’intérêt purement théorique de cette notion, et des « cardinaux infinis », on peut citer quelques exemples d'application. On les mentionne pour culture, mais ils supposent une certaine familiarité avec des notions non encore introduites.
Voici d’abord quelques exemples classiques d'ensembles dénombrables :
* $\mathbb {N} ^{*}$ est dénombrable ;
* $\mathbb {Z}$ est dénombrable ;
* $\mathbb {N} \times \mathbb {N}$ est dénombrable ;
* $\mathbb {Q}$ est dénombrable ;
* L'ensemble $\sqcup _{n\in \mathbb {N} ^{*}}\mathbb {Z} ^{n}$ des suites finies non vides d'entiers relatifs est dénombrable ;
* L'ensemble ${\mathcal {P}}_{\mathrm {f} }(\mathbb {N} )$des parties finies de $\mathbb {N}$ est dénombrable ;
* L'ensemble des nombres algébriques, c'est-à-dire des réels qui sont racines d'un polynôme non nul à coefficients entiers, est dénombrable.
* L'application $n\mapsto n+1$ est une bijection de $\mathbb {N}$ dans $\mathbb {N} ^{*}$.
* L'application $0\mapsto 0$, $1\mapsto 1$, $2\mapsto -1$, $3\mapsto 2$, $4\mapsto -2$… est une bijection de $\mathbb {N}$ dans $\mathbb {Z}$.
* La fonction de couplage de Cantor (illustration ci-contre) : $0\mapsto (0,0)$, $1\mapsto (1,0)$, $2\mapsto (0,1)$, $3\mapsto (2,0)$, $4\mapsto (1,1)$, $5\mapsto (0,2)$… est une bijection de $\mathbb {N}$ dans $\mathbb {N} \times \mathbb {N}$.
* D'après les trois points précédents, $\mathbb {Z} \times \mathbb {N} ^{*}$ est dénombrable. À partir d'une bijection $\mathbb {N} \to \mathbb {Z} \times \mathbb {N} ^{*},\,n\mapsto (p_{n},q_{n})$, on définit par récurrence une bijection $f:\mathbb {N} \to \mathbb {Q}$ en posant : $f(n):=p_{m}/q_{m}$, où $m$ est le plus petit entier tel que $p_{m}/q_{m}\notin \{f(k)\mid k<n\}$.
* Soit, pour tout $n\in \mathbb {N} ^{*}$, une bijection $f_{n}:\mathbb {N} \to \mathbb {Z} ^{n}$ obtenue grâce aux points 2 et 3. L'application $\mathbb {N} \times \mathbb {N} ^{*}\to \sqcup _{n\in \mathbb {N} ^{*}}\mathbb {Z} ^{n},\,(m,n)\mapsto f_{n}(m)$ est bijective, or $\mathbb {N} \times \mathbb {N} ^{*}$ est dénombrable d'après les points 1 et 3.
* À partir d'une bijection $\mathbb {N} \to \sqcup _{n\in \mathbb {N} }\mathbb {N} ^{n},\,n\mapsto \left(x_{1}^{n},\dots ,x_{k_{n}}^{n}\right)$ (construite comme au point précédent), on définit par récurrence une bijection $f:\mathbb {N} \to {\mathcal {P}}_{\mathrm {f} }(\mathbb {N} )$ en posant : $f(n):=\left\{x_{1}^{m},\dots ,x_{k_{m}}^{m}\right\}$, où $m$ est le plus petit entier tel que $\left\{x_{1}^{m},\dots ,x_{k_{m}}^{m}\right\}\notin \{f(k)\mid k<n\}$.
** L'ensemble $\mathbb {Z} [X]$ des polynômes à coefficients entiers est dénombrable.
** Le nombre de racines réelles d'un polynôme non nul est fini.

### Ensembles non dénombrables

La notion de cardinal d'un ensemble fini s'étend aux ensembles infinis ; par exemple :
On dit qu'un ensemble a pour cardinal $\aleph _{0}$ (lire « aleph-0 ») s'il est dénombrable.
On note $\aleph _{1}$ le plus petit cardinal infini non dénombrable.
En raisonnant par l'absurde, et en utilisant l'argument de la diagonale de Cantor, on peut démontrer que $\mathbb {R}$ n'est pas dénombrable. Mais démontrons plutôt un énoncé qui, au vu du théorème de Cantor ci-dessus, est plus précis :
$\mathbb {R}$ est équipotent à l'ensemble des parties de $\mathbb {N}$.
Il revient au même — en identifiant chaque partie de $\mathbb {N}$ à sa fonction indicatrice — d'affirmer que $\mathbb {R}$ est équipotent à l'ensemble $\{0,1\}^{\mathbb {N} }$ des suites de zéros et de uns. Parmi ces suites, notons N l'ensemble (dénombrable) constitué de la suite nulle et des suites qui se terminent par une infinité de uns, et X son complémentaire, qui contient un ensemble dénombrable (par exemple : les suites non nulles se terminant par une infinité de zéros). Alors (cf. exercice 1-4), $\{0,1\}^{\mathbb {N} }=X\cup N$ est équipotent à X, qui est en bijection (via les développements propres en base 2) avec l'intervalle réel ]0, 1[. Enfin, l'application $\left]0,1\right[\to \mathbb {R} ,\,x\mapsto {\frac {1}{x}}+{\frac {1}{x-1}}$ est bijective.
Par conséquent, $\left|\mathbb {R} \right|\geq \aleph _{1}$. On ne sait pas si $\left|\mathbb {R} \right|>\aleph _{1}$ ou $\left|\mathbb {R} \right|=\aleph _{1}$. On dit qu'un ensemble a la puissance du continu s'il est équipotent à $\mathbb {R}$. On fait souvent l'hypothèse du continu, qui consiste à admettre que $\left|\mathbb {R} \right|=\aleph _{1}$.
Puisque l’ensemble des entiers naturels est compris dans celui des nombres réels, et que l’ensemble des nombres réels n’est pas dénombrable, $\mathbb {R}$ est, au sens de l’injectabilité, « strictement plus grand » que $\mathbb {N}$. On en déduit un résultat important :
L'ensemble des nombres réels transcendants, c'est-à-dire non algébriques, a la puissance du continu.
L'ensemble Alg des réels algébriques est dénombrable (voir supra) donc n'est pas égal à $\mathbb {R}$ tout entier. L'ensemble Trans des réels transcendants est donc non vide ; il contient même un ensemble dénombrable (par exemple $\{t^{n}\mid n\in \mathbb {N} ^{*}\}$, où $t$ est un réel transcendant arbitraire). Par conséquent (exercice 1-4), Trans est équipotent à Trans ∪ Alg = $\mathbb {R}$.
A fortiori, l’ensemble $\mathbb {R} \setminus \mathbb {Q}$ des nombres irrationnels a la puissance du continu.