Avertissement

Ce contenu a été généré par une intelligence artificielle (LLM) et peut contenir des imprécisions ou des erreurs malgré notre relecture attentive. Il s'agit d'un outil d'apprentissage et non d'une référence académique.

Si vous constatez des erreurs, merci de nous les signaler via la page "À propos".

Comptage des applications (A)

---

Concept 1 : Le nombre d’applications entre ensembles finis

Prérequis

• Définition d’un ensemble fini et de son cardinal.
• Définition d’une application (domaine, codomaine, image).
• Produit cartésien d’ensembles.

Définition

Soient $E$ et $F$ deux ensembles finis. On note $\mathcal{F}(E, F)$ ou $F^E$ l’ensemble de toutes les applications de $E$ dans $F$.

Le cardinal (le nombre total) de ces applications est donné par :

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

Si on pose $|E| = k$ et $|F| = n$, alors le nombre d’applications est $n^k$.

Cette formule repose sur le principe multiplicatif : pour chaque élément de $E$, il y a $|F|$ choix possibles d’image dans $F$.

Propriétés clés

• Convention $0^0$ : Si $E = \varnothing$ et $F = \varnothing$, il existe exactement une application (l’application vide), donc $|\mathcal{F}(\varnothing, \varnothing)| = 0^0 = 1$.
• Ensemble de départ vide : Pour tout ensemble $F$, $|\mathcal{F}(\varnothing, F)| = |F|^0 = 1$. L’unique application est l’application vide.
• Ensemble d’arrivée vide : Si $E \neq \varnothing$ et $F = \varnothing$, alors $|\mathcal{F}(E, \varnothing)| = 0^{|E|} = 0$. Il est impossible d’associer une image à un élément de $E$.
• Bijection avec les $n$-uplets : L’ensemble $\mathcal{F}(E, F)$ est en bijection avec le produit cartésien $F \times \dots \times F$ ($|E|$ fois), noté $F^{|E|}$.

Exemples

Exemple 1 : Applications binaires

Soit $E = \{a, b, c\}$ ($|E|=3$) et $F = \{0, 1\}$ ($|F|=2$).

Le nombre d’applications de $E$ dans $F$ est :

$|F|^{|E|} = 2^3 = 8$

Une de ces applications est $f$ telle que $f(a)=0, f(b)=1, f(c)=0$.

Exemple 2 : Lancer de dés

On lance un dé standard (6 faces) 4 fois de suite. On peut modéliser cela comme une application de l’ensemble des lancers $E=\{1, 2, 3, 4\}$ vers l’ensemble des résultats possibles $F=\{1, 2, 3, 4, 5, 6\}$.

Le nombre total de séquences de résultats possibles est :

$6^4 = 1296$

Exemple 3 : Coloration

De combien de façons peut-on colorier 5 objets distincts avec 3 couleurs disponibles (Rouge, Vert, Bleu) ?

Ici, $E = \{\text{objets}\}$, $|E|=5$ et $F = \{\text{couleurs}\}$, $|F|=3$.

Chaque objet reçoit une couleur. Le nombre de coloriages est :

$3^5 = 243$

Contre-exemples

• Confusion base/exposant : Dans l’Exemple 1, le nombre d’applications n’est PAS $3^2 = 9$. Il est crucial de se rappeler que c’est $|\text{Arrivée}|^{|\text{Départ}|}$. Pensez : “pour chaque élément du départ, j’ai le choix de l’arrivée”.
• Ensembles infinis : Si $E = \mathbb{N}$ (infini), la formule $|F|^{|E|}$ au sens arithmétique standard ne s’applique pas directement pour donner un entier naturel. Ce concept est restreint aux ensembles finis dans ce chapitre.

Concepts liés

• Produit Cartésien : Le lien direct entre une application et un vecteur de ses images.
• Fonction caractéristique : Cas particulier où $F = \{0, 1\}$.

---

Concept 2 : Cardinal de l’ensemble des parties (Fonction caractéristique)

Prérequis

• Concept d’application (Concept 1).
• Définition de l’ensemble des parties $\mathcal{P}(E)$.
• Principe de bijection.

Définition

Soit $E$ un ensemble fini. Le nombre de sous-ensembles (ou parties) de $E$, noté $|\mathcal{P}(E)|$, est :

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

Pour démontrer cela, on utilise la fonction caractéristique (ou indicatrice) d’une partie $A \subseteq E$, notée $f_A$ ou $\mathbf{1}_A$, définie de $E$ vers $\{0, 1\}$ par :

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

Propriétés clés

• Bijection canonique : Il existe une bijection naturelle entre l’ensemble des parties $\mathcal{P}(E)$ et l’ensemble des applications $\mathcal{F}(E, \{0, 1\})$.
• Codage binaire : Chaque sous-ensemble peut être représenté de manière unique par une suite binaire de longueur $|E|$.
• Croissance : Le nombre de parties croît exponentiellement avec la taille de l’ensemble.

Exemples

Exemple 1 : Ensemble à 3 éléments

Soit $E = \{a, b, c\}$. $|E|=3$.

Le nombre de parties est $2^3 = 8$.

Les parties sont : $\varnothing, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}$.

La fonction caractéristique de $A=\{a, c\}$ correspond au triplet $(1, 0, 1)$ (1 pour $a$, 0 pour $b$, 1 pour $c$).

Exemple 2 : Interrupteurs

On dispose d’un panneau avec $n=10$ interrupteurs, chacun pouvant être allumé (ON) ou éteint (OFF). L’ensemble des interrupteurs allumés correspond à une partie de l’ensemble des 10 interrupteurs.

Le nombre de configurations possibles est :

$2^{10} = 1024$

Exemple 3 : Ensemble vide

Si $E = \varnothing$, alors $|E|=0$.

Le nombre de parties est $2^0 = 1$.

Cette unique partie est l’ensemble vide lui-même : $\mathcal{P}(\varnothing) = \{\varnothing\}$.

Contre-exemples

• Nombre de parties de taille fixe : La formule $2^{|E|}$ compte toutes les parties. Elle ne donne pas le nombre de parties ayant exactement $k$ éléments (ceci correspond au coefficient binomial $\binom{n}{k}$).
• Sous-ensembles ordonnés : $\mathcal{P}(E)$ contient des ensembles, où l’ordre ne compte pas. $\{a, b\}$ est la même partie que $\{b, a\}$. On ne compte pas deux fois.

Concepts liés

• Coefficients binomiaux : Lien via la somme $\sum_{k=0}^n \binom{n}{k} = 2^n$.
• Informatique : Représentation binaire des ensembles (bitmasks).

---

Concept 3 : Factorielle et Permutations

Prérequis

• Entiers naturels.
• Produit d’entiers.
• Définition d’une bijection.

Définition

La factorielle d’un entier naturel $n$, notée $n!$, est définie par :

$n! = \begin{cases} 1 & \text{si } n = 0 \\ 1 \times 2 \times \dots \times n = \prod_{i=1}^n i & \text{si } n \ge 1 \end{cases}$

Ceci correspond au nombre de permutations d’un ensemble fini $E$ de cardinal $n$ (c’est-à-dire le nombre de bijections de $E$ dans $E$).

Propriétés clés

• Récurrence : $n! = n \times (n-1)!$.
• Croissance très rapide : La factorielle croît plus vite que n’importe quelle fonction exponentielle $a^n$.
• Bijections : Si $|E| = |F| = n$, alors $|\mathcal{F}_{bij}(E, F)| = n!$.
• Approximation : Pour $n$ grand, $n! \approx \sqrt{2\pi n} (\frac{n}{e})^n$ (Formule de Stirling).

Exemples

Exemple 1 : Anagrammes simples

Combien de mots (ayant un sens ou non) peut-on former avec les lettres du mot “LOUP” ?

Les 4 lettres sont distinctes. Il s’agit de permuter 4 éléments.

Nombre de mots = $4! = 4 \times 3 \times 2 \times 1 = 24$.

Exemple 2 : Classement

Dans une course avec 8 participants, combien y a-t-il d’ordres d’arrivée possibles (sans ex aequo) ?

C’est le nombre de permutations de l’ensemble des 8 coureurs.

$8! = 40\,320$

Exemple 3 : Calcul avec simplification

Calculons $\frac{10!}{8!}$.

$\frac{10!}{8!} = \frac{10 \times 9 \times 8 \times \dots \times 1}{8 \times \dots \times 1} = 10 \times 9 = 90$

Contre-exemples

• Lettres répétées : Le nombre d’anagrammes de “MAMAN” n’est pas $5!$ car les lettres ne sont pas toutes distinctes (il y a répétition de M et A).
• Somme de factorielles : $(n+m)! \neq n! + m!$ et $(nm)! \neq n! \times m!$. Par exemple $(2+2)! = 24$ mais $2! + 2! = 4$.

Concepts liés

• Groupe symétrique $S_n$ : L’ensemble des permutations muni de la loi de composition.
• Formule de Stirling : Estimation asymptotique.

---

Concept 4 : Le nombre d’injections (Arrangements)

Prérequis

• Définition d’une injection ($f(x) = f(y) \implies x = y$).
• Factorielle (Concept 3).
• $|E| \le |F|$ pour qu’une injection existe (Principe des tiroirs).

Définition

Soient $E$ et $F$ deux ensembles finis avec $|E| = k$ et $|F| = n$.

Le nombre d’injections de $E$ dans $F$, noté $|\mathcal{F}_{inj}(E, F)|$, correspond au nombre de $k$-arrangements de $F$. Il est donné par :

undefined