Comptage des applications - fiches de révision (A)

Le nombre total d'applications de $E$ dans $F$, noté $|\mathcal{F}(E, F)|$ ou $|F^E|$, est :

$|F|^{|E|}$

Si on note $|E| = k$ (ensemble de départ) et $|F| = n$ (ensemble d'arrivée), la formule est :

$n^k$

Explication :

Pour chaque élément de $E$, il y a $|F|$ choix possibles pour son image. D'après le principe multiplicatif, on multiplie ces choix $|E|$ fois.

Le cardinal de l'ensemble des parties de $E$, noté $|\mathcal{P}(E)|$, est donné par :

$2^{|E|}$

Où :

• $|E|$ est le nombre d'éléments dans l'ensemble.

Pourquoi ?

Cela correspond au nombre d'applications de $E$ vers $\{0, 1\}$. Pour chaque élément, on a 2 choix : soit il est dans le sous-ensemble (1), soit il n'y est pas (0).

La factorielle de $n$, notée $n!$, est le produit des entiers de 1 à $n$ :

$n! = 1 \times 2 \times \dots \times n$

Signification combinatoire :

Elle représente le nombre de permutations d'un ensemble à $n$ éléments. C'est-à-dire le nombre de façons d'ordonner ces $n$ éléments distincts (ou le nombre de bijections de $E$ dans $E$).

Exemple :

Pour ordonner les lettres $\{A, B, C\}$, il y a $3! = 6$ façons.

Si $|E| = k$ et $|F| = n$, le nombre d'injections est noté $A_n^k$ et vaut :

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

Mais aussi $A_n^k = \binom{n}{k} \times k! = C_n^k \times k!$: c'est choisir $k$ éléments parmi $n$ (combinaison), puis les ordonner ($k!$ permutations).

Conditions :

• Il faut que $k \le n$ (sinon le nombre est 0).
• L'ordre compte et il n'y a pas de répétition.

Le nombre d'injections est nul si :

$|E| > |F|$

Explication (Principe des tiroirs) :

Si l'ensemble de départ a plus d'éléments que l'ensemble d'arrivée, il est impossible d'associer une image distincte à chaque élément de départ. Au moins deux éléments auront la même image.

Les nombres $S(n, k)$ (ou $\left\{ {n \atop k} \right\}$) comptent le nombre de façons de partitionner un ensemble de $n$ éléments en $k$ sous-ensembles non vides.

Points clés :

• L'ordre des sous-ensembles ne compte pas (les groupes sont indiscernables).
• Aucun sous-ensemble n'est vide.
• La réunion des sous-ensembles reforme l'ensemble total.

Si $|E| = n$ et $|F| = k$, le nombre de surjections est :

$k! \times S(n, k)$

Où :

• $S(n, k)$ est le nombre de Stirling de seconde espèce (façons de grouper les $n$ éléments en $k$ paquets).
• $k!$ correspond aux façons d'attribuer (ordonner) ces $k$ paquets aux $k$ éléments distincts de l'arrivée.

Condition : Il faut $n \ge k$.

Il s'agit d'une application quelconque (ou tirage avec remise).

Calcul :

• Ensemble de départ $E$ : les 4 lancers ($|E|=4$).
• Ensemble d'arrivée $F$ : les 6 faces possibles ($|F|=6$).

Le nombre de séquences est :

$|F|^{|E|} = 6^4 = 1296$

On n'utilise pas les arrangements car on peut obtenir le même chiffre plusieurs fois.

Soit $f: E \to F$, avec $|E|=n$ et $|F|=k$.

1. Injection ($n \le k$) : Chaque élément de l'arrivée est atteint au maximum une fois.
   • Formule : $\frac{k!}{(k-n)!}$ (Arrangements).
2. Surjection ($n \ge k$) : Chaque élément de l'arrivée est atteint au moins une fois.
   • Formule : $k! \cdot S(n, k)$.
3. Bijection ($n = k$) : Chaque élément de l'arrivée est atteint exactement une fois.
   • Formule : $n!$ (Permutations).

C'est une application qui permet de définir un sous-ensemble $A \subseteq E$. Elle est notée $\mathbf{1}_A : E \to \{0, 1\}$.

Définition :

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

Elle établit une bijection entre l'ensemble des parties $\mathcal{P}(E)$ et l'ensemble des applications $\mathcal{F}(E, \{0, 1\})$, justifiant la formule $2^{|E|}$.

Il s'agit d'un problème d'Arrangement (Injection), car l'ordre compte et il n'y a pas de répétition.

Données :

• On choisit $k=3$ chiffres.
• Parmi $n=5$ chiffres disponibles.

Calcul :

$A_5^3 = \frac{5!}{(5-3)!} = 5 \times 4 \times 3 = 60 \text{ codes.}$