Introduction aux mathématiques/Rudiments de combinatoire

Début de la boite de navigation du chapitre

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.

fin de la boite de navigation du chapitre

Définition

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

Ensembles finis

Pour tout $n\in \mathbb {N}$, on pose $\mathbb {N} _{n}=\{0,1,\dots ,n-1\}$, en particulier $\mathbb {N} _{0}=\varnothing$.

Proposition

Soit $p,n\in \mathbb {N}$. S'il existe une injection de $\mathbb {N} _{p}$ dans $\mathbb {N} _{n}$, alors $p\leq n$.

Démonstration

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 :

Corollaire

Soit $p,n\in \mathbb {N}$. $\mathbb {N} _{p}\sim \mathbb {N} _{n}$ (si et) seulement si $p=n$.

Ceci permet de définir

Définition : ensembles finis, cardinal

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

Début d'un lemme

Lemme

Soient E un ensemble fini et A une partie de E, alors A est fini et card(A) ≤ card(E).

Fin du lemme

Démonstration

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

Début d'un lemme

Lemme

1. Si E et F sont deux ensembles finis disjoints alors E∪F est fini et card(E∪F) = card(E) + card(F).
2. 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).

Fin du lemme

Démonstration

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

 

Corollaire 1

Soient E un ensemble fini et A une partie de E. Si card(A) = card(E), alors A = E.

Démonstration

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.

Corollaire 2 : cardinal d'une partition

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

Démonstration

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

 

Cas particulier d'une partition en parties équipotentes

Soient $E$ et $F$ deux ensembles finis. Alors $E\times F$ est fini, de cardinal $\left|E\right|\times \left|F\right|$.

Démonstration

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}$.

Corollaire 3

Si E et F sont deux ensembles finis alors E∪F est fini et card(E∪F) = card(E) + card(F) – card(E∩F).

Démonstration

On applique le lemme à E∪F = (E\F)∪(F\E)∪(F∩E) , E = (E\F)∪(E∩F) et F = (F\E)∪(E∩F).

 

Généralisation : formule du crible

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

Début d'un lemme

Lemme

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.

Fin du lemme

Démonstration

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

 

Corollaire

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

Proposition

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|}$.

Démonstration

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}$.

Corollaire

Si $E$ est fini alors l'ensemble ${\mathcal {P}}(E)$ des parties de $E$ est fini, de cardinal $2^{\left|E\right|}$.

Démonstration

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 ») :

Proposition

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

Début d’un théorème

Théorème de Cantor

Soit $E$ un ensemble. Alors il n'existe pas de surjection, et a fortiori pas de bijection, de $E$ sur ${\mathcal {P}}(E)$.

Fin du théorème

Démonstration

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 :

Proposition

Si un ensemble $E$ est infini, il existe une injection de $\mathbb {N}$ dans $E$.

Démonstration

À 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

Définition : 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 :

1. $\mathbb {N} ^{*}$ est dénombrable ;
2. $\mathbb {Z}$ est dénombrable ;
3. $\mathbb {N} \times \mathbb {N}$ est dénombrable ;
4. $\mathbb {Q}$ est dénombrable ;
5. L'ensemble $\sqcup _{n\in \mathbb {N} ^{*}}\mathbb {Z} ^{n}$ des suites finies non vides d'entiers relatifs est dénombrable ;
6. L'ensemble ${\mathcal {P}}_{\mathrm {f} }(\mathbb {N} )$des parties finies de $\mathbb {N}$ est dénombrable ;
7. 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.

Démonstration

La fonction de couplage de Cantor est une bijection de $\mathbb {N}$ dans $\mathbb {N} \times \mathbb {N}$.

1. L'application $n\mapsto n+1$ est une bijection de $\mathbb {N}$ dans $\mathbb {N} ^{*}$.
2. 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}$.
3. 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}$.
4. 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\}$.
5. 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.
6. À 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\}$.
7. • 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 :

Définition

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 :

Début d’un théorème

Théorème

$\mathbb {R}$ est équipotent à l'ensemble des parties de $\mathbb {N}$.

Fin du théorème

Démonstration

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 :

Début d’un théorème

Théorème

L'ensemble des nombres réels transcendants, c'est-à-dire non algébriques, a la puissance du continu.

Fin du théorème

Démonstration

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.