Comptage des applications - preuves (A)

Soit $E = \{x_1, x_2, \dots, x_k\}$ et $|F| = n$.

Pour construire une application $f : E \to F$, nous devons déterminer l'image de chaque élément de $E$.

Étape 1 : Choix des images

• Pour l'élément $x_1$, il y a $n$ choix possibles pour $f(x_1)$ (n'importe quel élément de $F$).
• Pour l'élément $x_2$, il y a également $n$ choix possibles pour $f(x_2)$ (les répétitions sont autorisées dans une application simple).
• ...
• Pour l'élément $x_k$, il y a $n$ choix possibles pour $f(x_k)$.

Étape 2 : Application du principe multiplicatif

Puisque le choix de l'image de chaque élément est indépendant des autres, le nombre total de façons de construire l'application est le produit des nombres de choix à chaque étape.

Nombre total $= \underbrace{n \times n \times \dots \times n}_{k \text{ fois}}$

Conclusion :

$|\mathcal{F}(E, F)| = n^k$

C'est-à-dire $|F|^{|E|}$.

Soit $E$ un ensemble fini. Nous cherchons à déterminer $|\mathcal{P}(E)|$.

Étape 1 : Définition de la fonction caractéristique

À chaque sous-ensemble $A \subseteq E$, on associe sa fonction caractéristique $\mathbf{1}_A : E \to \{0, 1\}$ définie par :

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

Étape 2 : Établissement de la bijection

Considérons l'application $\Phi : \mathcal{P}(E) \to \mathcal{F}(E, \{0, 1\})$ qui associe $A \mapsto \mathbf{1}_A$.

• Cette application est injective : Si deux parties $A$ et $B$ sont différentes, il existe un $x$ qui est dans l'une mais pas dans l'autre, donc $\mathbf{1}_A(x) \neq \mathbf{1}_B(x)$.
• Cette application est surjective : Pour toute fonction $f : E \to \{0, 1\}$, on peut construire l'ensemble $A = \{x \in E \mid f(x) = 1\}$, dont la fonction caractéristique est exactement $f$.

Ainsi, $\Phi$ est une bijection.

Étape 3 : Calcul du cardinal

Puisque $\Phi$ est une bijection, $|\mathcal{P}(E)| = |\mathcal{F}(E, \{0, 1\})|$.

D'après la formule du nombre d'applications (Concept 1), avec $|F|=|\{0, 1\}|=2$ :

$|\mathcal{F}(E, \{0, 1\})| = 2^{|E|}$

Conclusion :

$|\mathcal{P}(E)| = 2^{|E|}$

Démontrons par récurrence sur $n$ la proposition $P(n) :$ "Si $|E|=n$, alors $|\mathcal{P}(E)| = 2^n$".

Étape 1 : Initialisation ($n=0$)

Si $E = \varnothing$, alors la seule partie de $E$ est $\varnothing$.

$|\mathcal{P}(\varnothing)| = 1$.

Or $2^0 = 1$. La propriété est vraie pour $n=0$.

Étape 2 : Hérédité

Supposons que pour tout ensemble de cardinal $n$, le nombre de parties soit $2^n$.

Soit $E'$ un ensemble de cardinal $n+1$. Fixons un élément $a \in E'$ et posons $E = E' \setminus \{a\}$. Alors $|E| = n$.

Les parties de $E'$ peuvent être classées en deux types disjoints :

1. Les parties qui ne contiennent pas $a$ : ce sont exactement les parties de $E$. Il y en a $|\mathcal{P}(E)| = 2^n$ (par hypothèse de récurrence).
2. Les parties qui contiennent $a$ : chaque telle partie est de la forme $X \cup \{a\}$ où $X$ est une partie de $E$. Il y a autant de telles parties que de choix pour $X$, soit $2^n$.

Étape 3 : Somme

Le nombre total de parties de $E'$ est la somme des parties des deux types :

$|\mathcal{P}(E')| = 2^n + 2^n = 2 \times 2^n = 2^{n+1}$

Conclusion :

Par le principe de récurrence, pour tout $n \in \mathbb{N}$, $|\mathcal{P}(E)| = 2^n$.

Soit $E = \{x_1, \dots, x_n\}$. Une permutation est une bijection $\sigma : E \to E$. Cela revient à ordonner les éléments de $E$ dans une liste $(\sigma(x_1), \sigma(x_2), \dots, \sigma(x_n))$.

Étape 1 : Construction pas à pas

• Pour définir $\sigma(x_1)$, nous avons $n$ choix possibles parmi les éléments de $E$.
• Pour définir $\sigma(x_2)$, $\sigma$ devant être injective, nous ne pouvons pas reprendre la valeur de $\sigma(x_1)$. Il reste donc $n-1$ choix.
• Pour définir $\sigma(x_3)$, nous devons choisir une image distincte des deux précédentes. Il reste $n-2$ choix.
• ...
• Pour $\sigma(x_n)$, il ne reste plus qu'un seul élément disponible ($1$ choix).

Étape 2 : Calcul

D'après le principe multiplicatif, le nombre total de permutations est :

$n \times (n-1) \times (n-2) \times \dots \times 1$

Conclusion :

Ce produit correspond exactement à la définition de la factorielle.

$|\mathcal{S}_n| = n!$

Soit $E=\{x_1, \dots, x_k\}$ et $|F|=n$. Nous cherchons à construire une injection $f: E \to F$.

Étape 1 : Dénombrement des choix successifs

• Choix de $f(x_1)$ : $n$ possibilités dans $F$.
• Choix de $f(x_2)$ : Doit être différent de $f(x_1)$, donc $n-1$ possibilités.
• ...
• Choix de $f(x_i)$ : Doit être différent des $i-1$ images précédentes, donc $n-(i-1)$ possibilités.
• ...
• Choix de $f(x_k)$ : Doit être différent des $k-1$ images précédentes, donc $n-(k-1) = n - k + 1$ possibilités.

Étape 2 : Produit

Le nombre d'injections est :

$A_n^k = n \times (n-1) \times \dots \times (n-k+1)$

Étape 3 : Relation avec la factorielle

Pour exprimer cela avec des factorielles, on multiplie et divise par $(n-k)!$ :

$A_n^k = \frac{n(n-1)\dots(n-k+1) \times (n-k)(n-k-1)\dots 1}{(n-k)(n-k-1)\dots 1}$

Le numérateur devient le produit de $n$ jusqu'à $1$, soit $n!$.

Le dénominateur est le produit de $(n-k)$ jusqu'à $1$, soit $(n-k)!$.

Conclusion :

$|\mathcal{F}_{inj}(E, F)| = \frac{n!}{(n-k)!}$

Nous cherchons le nombre d'injections pour $k > n$.

Étape 1 : Raisonnement par le produit

Comme vu pour les arrangements, le nombre d'injections est le produit :

$P = n \times (n-1) \times \dots \times (n - k + 1)$

Ce produit contient $k$ termes (un pour chaque élément de $E$).

Étape 2 : Analyse des facteurs

Puisque $k > n$, c'est-à-dire $k \ge n+1$, la suite des facteurs va inclure le terme correspondant à l'étape $n+1$.

Regardons le terme général $(n - i + 1)$.

Pour $i = n+1$ (le $(n+1)$-ième élément à placer), le facteur est :

$n - (n+1) + 1 = 0$

Étape 3 : Annulation du produit

L'un des facteurs du produit est $0$. Par conséquent, le produit total est nul.

Alternativement, cela signifie qu'au moment de choisir une image pour le $(n+1)$-ième élément, toutes les $n$ valeurs de $F$ ont déjà été utilisées par les éléments précédents.

Conclusion :

Si $k > n$, $|\mathcal{F}_{inj}(E, F)| = 0$.

Soit $E = \{x_1, \dots, x_{n-1}, x_n\}$. Notons $x_n$ l'élément distingué.

On cherche à partitionner $E$ en $k$ parties non vides.

Cas 1 : Le singleton $\{x_n\}$ est une partie de la partition.

Si $\{x_n\}$ est l'un des $k$ sous-ensembles, alors les $n-1$ autres éléments doivent être partitionnés en les $k-1$ sous-ensembles restants.

Le nombre de façons de faire cela est par définition :

$S(n-1, k-1)$

Cas 2 : $\{x_n\}$ n'est pas une partie ( $x_n$ n'est pas seul).

Cela signifie que $x_n$ appartient à l'un des sous-ensembles formés par les autres éléments.

D'abord, on partitionne les $n-1$ autres éléments en $k$ sous-ensembles non vides. Il y a $S(n-1, k)$ façons de le faire.

Ensuite, on doit insérer $x_n$ dans l'un de ces $k$ groupes existants. Il y a $k$ choix possibles pour placer $x_n$.

Le nombre de façons pour ce cas est donc :

$k \times S(n-1, k)$

Conclusion :

Les deux cas étant disjoints et couvrant toutes les possibilités, on somme les résultats :

$S(n, k) = S(n-1, k-1) + k \cdot S(n-1, k)$

Pour $S(n, 1)$ :

On cherche le nombre de partitions de l'ensemble $E$ ($|E|=n$) en 1 seule partie.

La seule partie possible est $E$ lui-même (qui est non vide car $n \ge 1$).

La partition est donc $\{E\}$. Il n'y en a qu'une seule.

Donc $S(n, 1) = 1$.

Pour $S(n, n)$ :

On cherche le nombre de partitions de $E$ en $n$ parties non vides.

Puisqu'il y a $n$ éléments et $n$ parties, et qu'aucune partie ne doit être vide, chaque partie doit contenir exactement 1 élément.

La partition est donc nécessairement $\{ \{x_1\}, \{x_2\}, \dots, \{x_n\} \}$.

L'ordre des parties ne compte pas dans un ensemble (une partition est un ensemble de sous-ensembles). Il n'y a donc qu'une seule façon de former cette partition.

Donc $S(n, n) = 1$.

Conclusion :

Les égalités sont vérifiées.

Soit $\mathcal{S}$ l'ensemble des surjections de $E$ dans $F$.

Étape 1 : Partition induite par une surjection

Toute application $f$ définit une relation d'équivalence sur $E$ : $x \sim x' \iff f(x) = f(x')$.

Les classes d'équivalence sont les ensembles $f^{-1}(\{y\})$ pour $y \in F$.

Si $f$ est surjective, aucun de ces ensembles $f^{-1}(\{y\})$ n'est vide. De plus, il y a exactement $k$ classes d'équivalence (une pour chaque élément de $F$).

Ainsi, $f$ induit une partition de $E$ en $k$ parties non vides.

Étape 2 : De la partition à la surjection

Il y a $S(n, k)$ façons de partitionner $E$ en $k$ parties non vides $\{A_1, A_2, \dots, A_k\}$.

Pour construire une surjection à partir d'une telle partition, nous devons attribuer à chaque partie $A_i$ une image unique $y_j \in F$.

Cela revient à établir une bijection entre l'ensemble des parties de la partition (qui a $k$ éléments) et l'ensemble $F$ (qui a $k$ éléments).

Étape 3 : Calcul

Le nombre de bijections entre deux ensembles de taille $k$ est $k!$.

Pour chaque partition possible ($S(n, k)$ choix), il y a $k!$ façons d'assigner les images.

Nombre de surjections = (Nombre de partitions) $\times$ (Nombre d'assignations)

$|\mathcal{F}_{surj}(E, F)| = S(n, k) \times k!$

Conclusion :

La formule est prouvée.

Soit $E$ un ensemble tel que $|E| = n$.

Étape 1 : Partition de $\mathcal{P}(E)$ par cardinal

L'ensemble des parties $\mathcal{P}(E)$ peut être partitionné selon le nombre d'éléments dans chaque partie.

Soit $\mathcal{P}_k(E)$ l'ensemble des parties de $E$ ayant exactement $k$ éléments.

Puisque chaque partie a une taille unique comprise entre $0$ et $n$ :

$|\mathcal{P}(E)| = \sum_{k=0}^n |\mathcal{P}_k(E)|$

Étape 2 : Identification des termes

• Nous savons (Concept 2) que $|\mathcal{P}(E)| = 2^n$.
• Par définition des coefficients binomiaux, le nombre de parties de taille $k$ dans un ensemble de taille $n$ est $\binom{n}{k}$. Donc $|\mathcal{P}_k(E)| = \binom{n}{k}$.

Étape 3 : Égalité

En remplaçant dans l'équation de l'étape 1 :

$2^n = \sum_{k=0}^n \binom{n}{k}$

Conclusion :

La somme des coefficients binomiaux est bien égale à $2^n$.