Principes de dénombrement - fiches de révision (B)

La démonstration se fait en deux parties :

1. Condition suffisante ($\impliedby$) : Si $n \le m$, alors il existe une injection de $[n]$ dans $[m]$.

Cette implication est directe. L'application identité restreinte à $[n]$, $\iota : [n] \to [m]$ définie par $\iota(k)=k$ pour tout $k \in [n]$, est bien définie car si $k \in [n]$, alors $1 \le k \le n \le m$, donc $k \in [m]$. Elle est clairement injective car si $\iota(k_1) = \iota(k_2)$, alors $k_1=k_2$.

2. Condition nécessaire ($\implies$) : S'il existe une injection $f: [n] \to [m]$, alors $n \le m$.

On procède par récurrence sur $n$. Soit $P(n)$ l'assertion : "pour tout $m \in \mathbb{N}$, si $\exists f: [n] \to [m]$ injective, alors $n \le m$".

• Initialisation ($n=0$): L'ensemble $[0]$ est l'ensemble vide. L'application $f: \emptyset \to [m]$ est l'application vide. La condition $0 \le m$ est toujours vraie pour tout $m \in \mathbb{N}$. Donc $P(0)$ est vraie.

• Hérédité: Supposons que $P(n)$ est vraie pour un certain $n \in \mathbb{N}$. Montrons $P(n+1)$.

Soit $f: [n+1] \to [m]$ une injection. L'ensemble $[n+1]$ étant non vide, son image par $f$ est non vide, donc $[m]$ doit aussi être non vide, ce qui implique $m \ge 1$.

Soit $k = f(n+1) \in [m]$.

- **Cas 1 : $f(n+1) = m$**. La restriction de $f$ à $[n]$, notée $f|_{[n]}$, est une application de $[n]$ dans $[m-1]$ (car pour tout $i \in [n]$, $f(i) \neq f(n+1)=m$). Cette restriction est toujours injective. Par l'hypothèse de récurrence $P(n)$, l'existence d'une injection de $[n]$ dans $[m-1]$ implique $n \le m-1$. En ajoutant 1 de chaque côté, on obtient $n+1 \le m$.
- **Cas 2 : $f(n+1) = k \neq m$**. Soit $\sigma$ la transposition sur $[m]$ qui échange $k$ et $m$ (et laisse les autres éléments fixes). L'application $g = \sigma \circ f$ est une injection de $[n+1]$ dans $[m]$ car c'est la composée de deux injections. De plus, $g(n+1) = \sigma(f(n+1)) = \sigma(k) = m$. On est alors ramené au Cas 1 avec l'injection $g$. On en déduit que $n+1 \le m$.

Dans tous les cas, l'assertion est vraie pour $n+1$. Par le principe de récurrence, $P(n)$ est vraie pour tout $n \in \mathbb{N}$.

Théorème de Cantor-Bernstein

Soient $E$ et $F$ deux ensembles. S'il existe une injection de $E$ dans $F$ et une injection de $F$ dans $E$, alors $E$ et $F$ sont équipotents (c'est-à-dire qu'il existe une bijection entre $E$ et $F$).

Formellement :

$(\exists f: E \to F \text{ injective}) \land (\exists g: F \to E \text{ injective}) \implies (\exists h: E \to F \text{ bijective})$

Importance et application

Ce théorème est un outil extrêmement puissant en théorie des ensembles, particulièrement pour comparer les cardinaux d'ensembles infinis. Son importance réside dans le fait qu'il permet de prouver l'équipotence de deux ensembles sans avoir à construire explicitement une bijection entre eux.

La construction d'une bijection peut être très complexe. Il est souvent beaucoup plus simple de trouver deux injections dans des sens opposés.

Exemple d'utilisation : Pour prouver que $\mathbb{Q}$ est dénombrable (équipotent à $\mathbb{N}$), on montre :

1. Qu'il existe une injection de $\mathbb{N}$ dans $\mathbb{Q}$ (évident, $n \mapsto n/1$).
2. Qu'il existe une injection de $\mathbb{Q}$ dans $\mathbb{N} \times \mathbb{N}$ (en associant $p/q$ à $(p,q)$ après quelques ajustements pour le signe et l'unicité).

Comme $\mathbb{N} \times \mathbb{N}$ est équipotent à $\mathbb{N}$, on a une injection de $\mathbb{Q}$ dans $\mathbb{N}$. Le théorème de Cantor-Bernstein permet alors de conclure que $\mathbb{Q}$ et $\mathbb{N}$ sont équipotents.

C'est une application classique du principe des tiroirs de Dirichlet.

1. Définition des "objets" et des "tiroirs" :

• Les objets sont les $n+1$ entiers de l'ensemble $A$.
• Pour définir les tiroirs, on utilise le fait que tout entier $x \in [2n]$ peut s'écrire de manière unique sous la forme $x = 2^k \cdot v$, où $v$ est un entier impair et $k \ge 0$. L'entier $v$ est la partie impaire de $x$.
• Les tiroirs seront l'ensemble des parties impaires possibles pour un nombre dans $[2n]$. Les nombres impairs dans $[2n]$ sont $\{1, 3, 5, \dots, 2n-1\}$. Il y a exactement $n$ de ces nombres impairs.

2. Application du principe :

• On définit une application $f: A \to \{1, 3, \dots, 2n-1\}$ qui à chaque $a \in A$ associe sa partie impaire $v$.
• Nous avons $|A| = n+1$ objets (les éléments de $A$) et $n$ tiroirs (les parties impaires possibles).
• D'après le principe des tiroirs de Dirichlet, comme le nombre d'objets est strictement supérieur au nombre de tiroirs ($n+1 > n$), il doit exister au moins un tiroir contenant au moins deux objets.

3. Conclusion :

• Il existe donc deux éléments distincts $a_1, a_2 \in A$ qui ont la même partie impaire. Soit $v$ cette partie impaire commune.

• On peut donc écrire $a_1 = 2^{k_1} \cdot v$ et $a_2 = 2^{k_2} \cdot v$ pour des entiers $k_1, k_2 \ge 0$.

• Comme $a_1$ et $a_2$ sont distincts, on doit avoir $k_1 \neq k_2$.

• Supposons, sans perte de généralité, que $k_1 < k_2$. Alors on peut écrire :

  $a_2 = 2^{k_2} \cdot v = 2^{k_2-k_1} \cdot (2^{k_1} \cdot v) = 2^{k_2-k_1} \cdot a_1$

• Puisque $k_2 - k_1 > 0$, $2^{k_2-k_1}$ est un entier supérieur à 1. L'équation ci-dessus montre que $a_1$ divise $a_2$.

La démonstration se fait par l'absurde en utilisant un argument diagonal.

Soit $E$ un ensemble quelconque. Supposons par l'absurde qu'il existe une application surjective $f: E \to P(E)$. Cela signifie que pour tout sous-ensemble $A \subseteq E$ (donc $A \in P(E)$), il existe au moins un élément $y \in E$ tel que $f(y) = A$.

Considérons l'ensemble "diagonal" $D$ défini comme suit :

$D = \{x \in E \mid x \notin f(x) \}$

L'ensemble $D$ est un sous-ensemble de $E$ (il est formé d'éléments de $E$ qui n'appartiennent pas à leur propre image par $f$). Par conséquent, $D \in P(E)$.

Puisque nous avons supposé que $f$ est surjective, $D$ doit avoir un antécédent. C'est-à-dire qu'il doit exister un élément $y \in E$ tel que $f(y) = D$.

Analysons maintenant si cet élément $y$ peut appartenir à $D$ ou non.

• Cas 1 : $y \in D$.

  Par la définition de $D$, si $y \in D$, alors $y$ doit satisfaire la condition $y \notin f(y)$. Mais nous avons posé que $f(y) = D$. Donc, si $y \in D$, cela implique $y \notin D$. C'est une contradiction.

• Cas 2 : $y \notin D$.

  Par la définition de $D$, si $y \notin D$, cela signifie que $y$ ne satisfait pas la condition d'appartenance à $D$. La négation de "$x \notin f(x)$" est "$x \in f(x)$". Donc, si $y \notin D$, cela implique $y \in f(y)$. Mais encore une fois, comme $f(y) = D$, cela implique $y \in D$. C'est aussi une contradiction.

Dans les deux cas possibles, nous arrivons à une contradiction de la forme $P \iff \neg P$. L'hypothèse de départ, à savoir l'existence d'une application surjective $f: E \to P(E)$, doit donc être fausse.

Conclusion : Il n'existe aucune surjection de $E$ dans $P(E)$, et par conséquent, il n'existe pas de bijection. Cela implique que $|E| < |P(E)|$ pour tout ensemble $E$.

Principe des bergers (cas régulier)

Soient $E$ et $F$ deux ensembles finis et $f: E \to F$ une application surjective. Si toutes les préimages (ou fibres) des éléments de $F$ ont le même cardinal $p$ (c'est-à-dire $\forall y \in F, |f^{-1}(\{y\})| = p$), alors le cardinal de $E$ est lié au cardinal de $F$ par la relation :

$|E| = p \cdot |F|$

Ce principe est souvent utilisé pour trouver le cardinal de $F$ (les "moutons") en comptant un ensemble $E$ plus simple (les "pattes") et en divisant par $p$ (le nombre de pattes par mouton).

Application : Preuve du Théorème de Lagrange

Théorème de Lagrange : Soit $G$ un groupe fini et $H$ un sous-groupe de $G$. Alors l'ordre (le cardinal) de $H$ divise l'ordre de $G$.

Démonstration avec le principe des bergers :

1. Définir les ensembles $E$, $F$ et l'application $f$ :

   • Soit $E = G$, le groupe lui-même.
   • Soit $F = G/H = \{gH \mid g \in G\}$, l'ensemble des classes à gauche de $G$ suivant $H$.
   • Soit $f: G \to G/H$ l'application de projection canonique définie par $f(g) = gH$.

2. Vérifier les conditions du principe :

   • Surjectivité : L'application $f$ est surjective par définition même de l'ensemble quotient $G/H$. Toute classe $gH \in G/H$ est l'image de $g \in G$ (et de tous les autres éléments de la classe).

   • Fibres de taille constante : La fibre d'un élément $gH \in G/H$ est l'ensemble de tous les éléments $x \in G$ tels que $f(x) = gH$.

     $f^{-1}(\{gH\}) = \{x \in G \mid xH = gH \}$

     On sait que $xH=gH \iff g^{-1}x \in H \iff x \in gH$. Donc, la fibre de $gH$ est précisément la classe $gH$ elle-même.

     Toutes les classes à gauche ont le même cardinal que le sous-groupe $H$. En effet, l'application $\phi: H \to gH$ définie par $\phi(h) = gh$ est une bijection. Le cardinal de chaque fibre est donc $p = |H|$.

3. Appliquer la formule :

   Puisque les conditions du principe des bergers (cas régulier) sont remplies, on a :

   $|G| = |H| \cdot |G/H|$

   L'entier $|G/H|$ est appelé l'indice de $H$ dans $G$, noté $[G:H]$. La relation montre que $|G|$ est un multiple entier de $|H|$, ce qui signifie que $|H|$ divise $|G|$.

La preuve utilise le principe des tiroirs de Dirichlet de manière ingénieuse.

Soit une séquence $S = (a_1, a_2, \dots, a_{N})$ avec $N = n^2+1$ et les $a_i$ sont des réels distincts.

1. Définition des objets et des tiroirs :

• Les objets sont les $N = n^2+1$ termes de la séquence, $a_1, \dots, a_{N}$.
• Pour chaque terme $a_i$ de la séquence, on associe un couple d'entiers $(x_i, y_i)$ où :
  • $x_i$ est la longueur de la plus longue sous-séquence croissante se terminant par $a_i$.
  • $y_i$ est la longueur de la plus longue sous-séquence décroissante se terminant par $a_i$.
• Les tiroirs sont les couples $(x,y)$ possibles.

2. Hypothèse par l'absurde :

Supposons que le théorème est faux. Cela signifie qu'il n'existe aucune sous-séquence monotone de longueur $n+1$.

Par conséquent, pour chaque $i \in \{1, \dots, N\}$, les longueurs $x_i$ et $y_i$ doivent être au plus $n$.

$1 \le x_i \le n \quad \text{et} \quad 1 \le y_i \le n$

Le nombre total de tiroirs (couples $(x_i, y_i)$ possibles) est donc $n \times n = n^2$.

3. Application du principe des tiroirs :

Nous avons $n^2+1$ objets (les termes $a_i$) à placer dans $n^2$ tiroirs (les couples $(x_i, y_i)$).

Par le principe des tiroirs, il doit exister au moins deux objets qui sont dans le même tiroir. Autrement dit, il existe deux indices distincts $i < j$ tels que :

$(x_i, y_i) = (x_j, y_j)$

Ce qui signifie $x_i = x_j$ et $y_i = y_j$.

4. Recherche de la contradiction :

Considérons les termes $a_i$ et $a_j$ avec $i < j$. Puisque tous les termes de la séquence sont distincts, on a soit $a_i < a_j$, soit $a_i > a_j$.

• Cas 1 : $a_i < a_j$

  Puisque $a_i < a_j$, on peut prendre la plus longue sous-séquence croissante se terminant par $a_i$ (de longueur $x_i$) et y ajouter $a_j$ à la fin pour former une nouvelle sous-séquence croissante se terminant par $a_j$. La longueur de cette nouvelle sous-séquence est au moins $x_i + 1$.

  Cela implique que $x_j \ge x_i + 1$. Mais cela contredit notre conclusion du principe des tiroirs, qui était $x_i = x_j$.

• Cas 2 : $a_i > a_j$

  De la même manière, puisque $a_i > a_j$, on peut prendre la plus longue sous-séquence décroissante se terminant par $a_i$ (de longueur $y_i$) et y ajouter $a_j$ pour former une nouvelle sous-séquence décroissante se terminant par $a_j$. Sa longueur est au moins $y_i + 1$.

  Cela implique que $y_j \ge y_i + 1$. Mais cela contredit notre conclusion $y_i = y_j$.

Dans tous les cas, nous arrivons à une contradiction. L'hypothèse initiale (l'absence de sous-séquence monotone de longueur $n+1$) doit donc être fausse.

Selon le principe de bijection, pour prouver que $|P(E)| = 2^n$, il suffit de construire une bijection entre $P(E)$ (l'ensemble des parties de $E$) et un ensemble dont le cardinal est connu pour être $2^n$.

L'ensemble que nous utiliserons est $\{0,1\}^E$, l'ensemble de toutes les fonctions de $E$ dans l'ensemble $\{0,1\}$. Par le principe de multiplication, le cardinal de cet ensemble est $|\{0,1\}|^{|E|} = 2^n$.

Construction de la bijection :

Soit $\phi: P(E) \to \{0,1\}^E$ l'application qui, à chaque sous-ensemble $A \subseteq E$, associe sa fonction caractéristique $\chi_A: E \to \{0,1\}$.

La fonction caractéristique $\chi_A$ est définie par :

$\chi_A(x) = \begin{cases} 1 & \text{si } x \in A \\ 0 & \text{si } x \notin A \end{cases}$

Cette fonction "indique" si un élément de $E$ appartient ou non au sous-ensemble $A$.

Preuve que $\phi$ est une bijection :

Pour montrer que $\phi$ est une bijection, nous montrons qu'elle est injective et surjective.

1. Injectivité : Soient $A$ et $B$ deux sous-ensembles de $E$ tels que $\phi(A) = \phi(B)$. Cela signifie que leurs fonctions caractéristiques sont égales, i.e., $\chi_A = \chi_B$. Par définition, cela veut dire que pour tout $x \in E$, $\chi_A(x) = \chi_B(x)$.

   • Si $\chi_A(x) = 1$, alors $x \in A$. Comme $\chi_B(x) = 1$ aussi, on a $x \in B$.
   • Si $\chi_A(x) = 0$, alors $x \notin A$. Comme $\chi_B(x) = 0$ aussi, on a $x \notin B$.

   Un élément est donc dans $A$ si et seulement s'il est dans $B$. Cela signifie que $A=B$. L'application $\phi$ est donc injective.

2. Surjectivité : Soit $f$ une fonction quelconque dans $\{0,1\}^E$. Nous devons trouver un sous-ensemble $A \in P(E)$ tel que $\phi(A) = f$.

   Considérons l'ensemble $A_f = \{x \in E \mid f(x) = 1\}$. C'est bien un sous-ensemble de $E$.

   La fonction caractéristique de $A_f$, notée $\chi_{A_f}$, est par définition :

   • $\chi_{A_f}(x) = 1$ si $x \in A_f$, ce qui par construction de $A_f$ signifie $f(x)=1$.
   • $\chi_{A_f}(x) = 0$ si $x \notin A_f$, ce qui par construction de $A_f$ signifie $f(x)=0$.

   Donc, $\chi_{A_f}(x) = f(x)$ pour tout $x \in E$, ce qui signifie que $\chi_{A_f} = f$.

   Nous avons trouvé un antécédent pour $f$, donc $\phi$ est surjective.

Puisque $\phi$ est à la fois injective et surjective, c'est une bijection. Par le principe de bijection, on a :

$|P(E)| = |\{0,1\}^E| = 2^n$

Formule de Poincaré (Principe d'inclusion-exclusion généralisé)

Soient $E_1, E_2, \dots, E_n$ des ensembles finis. Le cardinal de leur union est donné par :

$\left| \bigcup_{i=1}^n E_i \right| = \sum_{\emptyset \neq I \subseteq [n]} (-1)^{|I|-1} \left| \bigcap_{i \in I} E_i \right|$

où $[n] = \{1, 2, \dots, n\}$.

En l'écrivant de manière plus explicite :

$\left| \bigcup_{i=1}^n E_i \right| = \sum_{i} |E_i| - \sum_{i<j} |E_i \cap E_j| + \sum_{i<j<k} |E_i \cap E_j \cap E_k| - \dots + (-1)^{n-1} |E_1 \cap \dots \cap E_n|$

Intuition derrière l'alternance des signes

L'objectif est de s'assurer que chaque élément de l'union est compté exactement une fois.

Considérons un élément $x$ qui appartient à exactement $k$ des ensembles $E_i$ (avec $1 \le k \le n$). Voyons combien de fois il est compté dans la formule :

1. Terme $\sum |E_i|$ : $x$ est compté dans $|E_i|$ pour chacun des $k$ ensembles auxquels il appartient. Il est donc compté $\binom{k}{1}$ fois. (Sur-comptage)
2. Terme $-\sum |E_i \cap E_j|$ : $x$ est dans l'intersection de n'importe quelle paire de ces $k$ ensembles. Il y a $\binom{k}{2}$ telles paires. Il est donc soustrait $\binom{k}{2}$ fois.
3. Terme $+\sum |E_i \cap E_j \cap E_k|$ : De même, il est ajouté $\binom{k}{3}$ fois.
4. Et ainsi de suite...

Le nombre total de fois où $x$ est compté est :

$\text{Nombre de comptages de } x = \binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \dots + (-1)^{k-1} \binom{k}{k}$

Nous connaissons l'identité du binôme de Newton :

$(a+b)^k = \sum_{j=0}^k \binom{k}{j} a^{k-j} b^j$

En posant $a=1$ et $b=-1$, on obtient :

$(1-1)^k = \binom{k}{0} - \binom{k}{1} + \binom{k}{2} - \dots + (-1)^k \binom{k}{k}$

$0 = 1 - \left( \binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \dots + (-1)^{k-1} \binom{k}{k} \right)$

Donc, la somme entre parenthèses vaut exactement 1.

$\binom{k}{1} - \binom{k}{2} + \dots + (-1)^{k-1} \binom{k}{k} = 1$

Chaque élément de l'union est donc compté précisément une fois, ce qui prouve la validité de la formule. L'alternance des signes est le mécanisme qui corrige successivement les sur-comptages et sous-comptages à chaque étape.

Définition de l'Hypothèse du Continu (HC)

L'Hypothèse du Continu est une conjecture en théorie des ensembles, formulée par Georg Cantor, qui concerne la taille des ensembles infinis. Elle s'énonce comme suit :

Il n'existe aucun ensemble dont le cardinal est strictement compris entre le cardinal de l'ensemble des entiers naturels ($\mathbb{N}$) et le cardinal de l'ensemble des nombres réels ($\mathbb{R}$).

En utilisant la notation des cardinaux transfinis :

• Le cardinal de $\mathbb{N}$ est noté $\aleph_0$ (aleph-zéro), le plus petit cardinal infini.
• Le cardinal de $\mathbb{R}$ est noté $\mathfrak{c}$ (la puissance du continu). On peut montrer que $\mathfrak{c} = |P(\mathbb{N})| = 2^{\aleph_0}$.

L'Hypothèse du Continu affirme donc qu'il n'existe pas d'ensemble $S$ tel que $\aleph_0 < |S| < \mathfrak{c}$.

Statut dans la théorie des ensembles ZFC

Le statut de l'Hypothèse du Continu au sein du système axiomatique standard de la théorie des ensembles, Zermelo-Fraenkel avec l'axiome du choix (ZFC), est qu'elle est indécidable.

Cela signifie que :

1. On ne peut pas prouver que l'Hypothèse du Continu est vraie à partir des axiomes de ZFC.
2. On ne peut pas réfuter l'Hypothèse du Continu (prouver qu'elle est fausse) à partir des axiomes de ZFC.

Ce résultat a été établi en deux étapes majeures :

• Kurt Gödel (1940) a montré que l'Hypothèse du Continu est consistante avec ZFC. Il a prouvé que si ZFC est exempt de contradiction, alors ZFC + HC l'est aussi. On ne peut donc pas réfuter HC dans ZFC.
• Paul Cohen (1963) a montré que la négation de l'Hypothèse du Continu est également consistante avec ZFC. Il a prouvé que si ZFC est exempt de contradiction, alors ZFC + $\neg$HC l'est aussi. On ne peut donc pas prouver HC dans ZFC.

En résumé, l'Hypothèse du Continu est indépendante des axiomes de ZFC. On peut choisir de l'accepter comme un nouvel axiome ou d'accepter sa négation, donnant lieu à des "univers mathématiques" différents, tous deux compatibles avec ZFC.

Soit $C$ l'ensemble des chemins sur un quadrillage allant de $(0,0)$ à $(m,n)$ avec des pas unitaires vers la droite (R) ou vers le haut (U).

Analyse du problème :

• Pour aller de l'abscisse 0 à l'abscisse $m$, un chemin doit effectuer exactement $m$ pas vers la droite (R).
• Pour aller de l'ordonnée 0 à l'ordonnée $n$, un chemin doit effectuer exactement $n$ pas vers le haut (U).
• Par conséquent, tout chemin de $(0,0)$ à $(m,n)$ est une séquence de longueur totale $m+n$, composée de exactement $m$ pas 'R' et $n$ pas 'U'.

Exemple : Pour aller à $(2,1)$, un chemin possible est RRU, un autre est RUR.

Construction de la bijection :

Le problème se ramène à compter le nombre de ces séquences. Nous pouvons établir une bijection entre l'ensemble des chemins $C$ et un ensemble plus facile à dénombrer.

Soit $S = \{1, 2, \dots, m+n\}$ l'ensemble des positions dans la séquence de pas.

Un chemin est entièrement déterminé par le choix des positions où l'on place les $m$ pas 'R' (les positions restantes seront obligatoirement occupées par les pas 'U').

Soit $P_m(S)$ l'ensemble de tous les sous-ensembles de $S$ de cardinal $m$. On sait que $|P_m(S)| = \binom{m+n}{m}$.

On définit une application $\phi: C \to P_m(S)$ de la manière suivante :

Pour un chemin $c \in C$, $\phi(c)$ est l'ensemble des indices (positions) dans la séquence où un pas 'R' est effectué.

Exemple : Pour un chemin de $(0,0)$ à $(3,2)$, la séquence RURRU correspond au sous-ensemble $\{1, 3, 4\}$ de $\{1,2,3,4,5\}$.

Preuve que $\phi$ est une bijection :

• Injectivité : Si deux chemins $c_1$ et $c_2$ sont différents, leurs séquences de pas sont différentes. Cela signifie qu'il existe au moins une position $i$ où l'un a un 'R' et l'autre un 'U'. Par conséquent, l'ensemble des positions des 'R' sera différent pour $c_1$ et $c_2$, donc $\phi(c_1) \neq \phi(c_2)$.
• Surjectivité : Soit $A$ un sous-ensemble quelconque de $S$ de cardinal $m$. On peut construire un chemin unique $c_A$ en plaçant des 'R' aux positions données par $A$ et des 'U' dans les $n$ positions restantes. Ce chemin $c_A$ a bien $m$ pas 'R' et $n$ pas 'U', et il est clair que $\phi(c_A) = A$. Donc, tout élément de $P_m(S)$ a un antécédent.

Puisque $\phi$ est une bijection, on a $|C| = |P_m(S)|$.

Conclusion :

Le nombre de chemins est :

$|C| = \binom{m+n}{m}$

Par la symétrie des coefficients binomiaux, ce nombre est aussi égal à $\binom{m+n}{n}$, ce qui correspondrait à choisir les positions des $n$ pas 'U'.

Un ensemble est dénombrable s'il est équipotent à l'ensemble des entiers naturels $\mathbb{N}$. Pour prouver que $|\mathbb{Q}| = |\mathbb{N}|$, nous utilisons le Théorème de Cantor-Bernstein. Il suffit de montrer qu'il existe une injection de $\mathbb{N}$ dans $\mathbb{Q}$ et une injection de $\mathbb{Q}$ dans $\mathbb{N}$.

1. Existence d'une injection $f: \mathbb{N} \to \mathbb{Q}$

Cette partie est triviale. L'application d'inclusion $f(n) = \frac{n}{1}$ est une injection de $\mathbb{N}$ dans $\mathbb{Q}$. Cela prouve que $|\mathbb{N}| \le |\mathbb{Q}|$.

2. Existence d'une injection $g: \mathbb{Q} \to \mathbb{N}$

Cette partie est plus complexe. Nous construisons l'injection par étapes.

• Étape 2a : Injection de $\mathbb{Q}$ dans $\mathbb{Z} \times \mathbb{N}^*$

  Tout nombre rationnel $q \in \mathbb{Q}$ peut s'écrire de manière unique comme une fraction irréductible $\frac{p}{s}$ avec $p \in \mathbb{Z}$, $s \in \mathbb{N}^* = \{1, 2, 3, \dots\}$ et $\text{pgcd}(p,s)=1$.

  On définit l'application $g_1: \mathbb{Q} \to \mathbb{Z} \times \mathbb{N}^*$ par $g_1(q) = (p,s)$. Cette application est injective par l'unicité de la représentation en fraction irréductible.

• Étape 2b : Injection de $\mathbb{Z} \times \mathbb{N}^*$ dans $\mathbb{N} \times \mathbb{N}$

  On définit une bijection $h_{\mathbb{Z}}: \mathbb{Z} \to \mathbb{N}$ par :

  $h_{\mathbb{Z}}(z) = \begin{cases} 2z & \text{si } z \ge 0 \\ -2z-1 & \text{si } z < 0 \end{cases}$

  L'application identité sur $\mathbb{N}^*$ est une injection de $\mathbb{N}^*$ dans $\mathbb{N}$.

  On peut donc construire une injection $g_2: \mathbb{Z} \times \mathbb{N}^* \to \mathbb{N} \times \mathbb{N}$ en appliquant $h_{\mathbb{Z}}$ à la première composante et l'identité à la seconde.

• Étape 2c : Injection de $\mathbb{N} \times \mathbb{N}$ dans $\mathbb{N}$

  Il existe plusieurs bijections (et donc injections) entre $\mathbb{N} \times \mathbb{N}$ et $\mathbb{N}$. Une des plus connues est la fonction de couplage de Cantor :

  $g_3(a,b) = \frac{1}{2}(a+b)(a+b+1) + b$

  Cette fonction est une bijection, donc elle est injective.

• Conclusion de l'étape 2 :

  L'application $g = g_3 \circ g_2 \circ g_1$ est une injection de $\mathbb{Q}$ dans $\mathbb{N}$, car c'est une composition d'injections. Cela prouve que $|\mathbb{Q}| \le |\mathbb{N}|$.

3. Conclusion finale

Nous avons montré que $|\mathbb{N}| \le |\mathbb{Q}|$ et $|\mathbb{Q}| \le |\mathbb{N}|$. Par le Théorème de Cantor-Bernstein, nous pouvons conclure que $|\mathbb{Q}| = |\mathbb{N}|$. L'ensemble $\mathbb{Q}$ est donc dénombrable.

La démonstration se fait par l'absurde.

Hypothèses :

• Soit $E$ l'ensemble des objets, avec $|E|=m$.
• Soit $F = \{t_1, t_2, \dots, t_n\}$ l'ensemble des tiroirs, avec $|F|=n$.
• Soit $f: E \to F$ l'application qui associe chaque objet à son tiroir.
• La taille du tiroir $t_i$ est le cardinal de sa préimage, $|f^{-1}(\{t_i\})|$.

Assertion à prouver :

Il existe au moins un tiroir $t_i \in F$ tel que $|f^{-1}(\{t_i\})| \ge \lceil m/n \rceil$.

Preuve par l'absurde :

Supposons que l'assertion est fausse. Cela signifie que tous les tiroirs contiennent strictement moins de $\lceil m/n \rceil$ objets.

Pour tout $i \in \{1, \dots, n\}$, on a :

$|f^{-1}(\{t_i\})| < \lceil m/n \rceil$

Puisque le nombre d'objets $|f^{-1}(\{t_i\})|$ est un entier, cette inégalité stricte est équivalente à :

$|f^{-1}(\{t_i\})| \le \lceil m/n \rceil - 1$

La famille des préimages $\{f^{-1}(\{t_i\})\}_{i=1}^n$ forme une partition de l'ensemble $E$. Par le principe d'addition, le nombre total d'objets est la somme du nombre d'objets dans chaque tiroir :

$|E| = m = \sum_{i=1}^n |f^{-1}(\{t_i\})|$

En utilisant notre supposition, nous pouvons majorer cette somme :

$m = \sum_{i=1}^n |f^{-1}(\{t_i\})| \le \sum_{i=1}^n \left( \lceil m/n \rceil - 1 \right) = n \left( \lceil m/n \rceil - 1 \right)$

Rappelons la propriété de la fonction plafond : pour tout réel $x$, on a $x \le \lceil x \rceil < x+1$.

En appliquant la deuxième partie de cette inégalité avec $x=m/n$, on a $\lceil m/n \rceil < m/n + 1$.

Substituons cela dans notre majoration de $m$ :

$m \le n \left( \lceil m/n \rceil - 1 \right) < n \left( (m/n + 1) - 1 \right) = n (m/n) = m$

Nous obtenons ainsi l'inégalité stricte $m < m$, ce qui est une contradiction.

L'hypothèse de départ doit donc être fausse. Par conséquent, il existe au moins un tiroir $t_i$ tel que $|f^{-1}(\{t_i\})| \ge \lceil m/n \rceil$.