Applications et dénombrement : cours de maths Licence L1

Rate this post

Cours de maths en Licence L1 : Applications et dénombrement — Zyro, l’explorateur de Planète Maths

Dire qu’un objet mathématique « est bien défini », compter des configurations sans les écrire une à une, prouver qu’un phénomène se produit forcément : trois gestes qui reposent sur la notion d’application et sur l’art du dénombrement. Ce chapitre fixe le vocabulaire des applications (injection, surjection, bijection, images directe et réciproque, composition), puis développe les outils pour compter : cardinaux, arrangements, combinaisons, formule du binôme et principe des tiroirs.

Sommaire

1. Applications entre ensembles

Application

Soient \(E\) et \(F\) deux ensembles. Une application \(f : E \to F\) associe à chaque élément \(x\) de \(E\) un unique élément \(f(x)\) de \(F\). L’ensemble \(E\) est l’ensemble de départ, \(F\) l’ensemble d’arrivée. Si \(y = f(x)\), on dit que \(y\) est l’image de \(x\) et que \(x\) est un antécédent de \(y\).

Deux conditions sont donc exigées : aucun élément de \(E\) ne reste sans image, et aucun n’en possède deux. Ainsi \(x \mapsto \dfrac{1}{x}\) n’est pas une application de \(\mathbb{R}\) dans \(\mathbb{R}\) (le réel \(0\) n’a pas d’image), mais c’en est une de \(\mathbb{R}^*\) dans \(\mathbb{R}\). Deux applications sont égales lorsqu’elles ont mêmes ensembles de départ et d’arrivée et mêmes images en tout point. L’application identité de \(E\), notée \(\mathrm{id}_E\), envoie chaque \(x\) sur lui-même.

2. Injection, surjection, bijection

Trois propriétés fondamentales

Soit \(f : E \to F\).

\(f\) est injective si deux éléments distincts ont toujours des images distinctes : \(\forall (x, x') \in E^2,\; f(x) = f(x') \Rightarrow x = x'\). Chaque élément de \(F\) a au plus un antécédent.
\(f\) est surjective si tout élément de \(F\) est une image : \(\forall y \in F,\; \exists x \in E,\; f(x) = y\). Chaque élément de \(F\) a au moins un antécédent.
\(f\) est bijective si elle est à la fois injective et surjective : chaque élément de \(F\) a exactement un antécédent.

Les trois diagrammes ci-dessus illustrent chaque situation : une injection (un élément de \(F\), la lettre \(c\), n’est pas atteint), une surjection (deux flèches arrivent en \(y\)) et une bijection (une flèche exactement par élément d’arrivée).

Méthode : prouver qu’une application est injective ou surjective

Injectivité : on suppose \(f(x) = f(x')\) et on en déduit \(x = x'\). Pour la réfuter, on exhibe deux éléments distincts de même image.
Surjectivité : on fixe \(y\) dans \(F\) et on résout l’équation \(f(x) = y\) d’inconnue \(x\) dans \(E\). Pour la réfuter, on exhibe un \(y\) sans antécédent.

Exemple 1

Soit \(f : \mathbb{R} \to \mathbb{R}\), \(f(x) = 4x - 5\). Si \(f(x) = f(x')\), alors \(4x - 5 = 4x' - 5\), donc \(x = x'\) : \(f\) est injective. Pour \(y \in \mathbb{R}\), l’équation \(4x - 5 = y\) a pour solution \(x = \dfrac{y + 5}{4} \in \mathbb{R}\) : \(f\) est surjective. Elle est donc bijective.

En revanche \(g : \mathbb{R} \to \mathbb{R}\), \(g(x) = x^2\) n’est ni injective (\(g(-2) = g(2) = 4\)) ni surjective (\(-1\) n’a aucun antécédent). Mais \(g\) restreinte à \(\mathbb{R}_+\) au départ et à l’arrivée est bijective.

Attention à l’ensemble d’arrivée

La surjectivité dépend de \(F\) : \(x \mapsto x^2\) n’est pas surjective de \(\mathbb{R}\) dans \(\mathbb{R}\), mais elle l’est de \(\mathbb{R}\) dans \(\mathbb{R}_+\). Précisez toujours départ et arrivée avant de conclure.

3. Image directe et image réciproque

Images directe et réciproque

Soit \(f : E \to F\). Pour \(A \subset E\), l’image directe est \(f(A) = \{ f(x) \;;\; x \in A \}\). Pour \(B \subset F\), l’image réciproque est \(f^{-1}(B) = \{ x \in E \;;\; f(x) \in B \}\).

La notation \(f^{-1}(B)\) désigne un sous-ensemble de \(E\) et ne suppose pas que \(f\) soit bijective. Sur la parabole ci-dessous, l’image directe de \([-1\,;\,2]\) par \(x \mapsto x^2\) se lit sur l’axe des ordonnées.

Exemple 2

Pour \(f(x) = x^2\) sur \(\mathbb{R}\) : \(f([-1\,;\,2]) = [0\,;\,4]\) (le minimum \(0\) est atteint en \(0\), le maximum \(4\) en \(2\)). Et \(f^{-1}([1\,;\,4]) = [-2\,;\,-1] \cup [1\,;\,2]\), car \(1 \le x^2 \le 4\) équivaut à \(1 \le |x| \le 2\). Enfin \(f^{-1}([-3\,;\,-1]) = \varnothing\).

Propriétés

Pour \(A, A' \subset E\) et \(B, B' \subset F\) :

\(f(A \cup A') = f(A) \cup f(A')\) et \(f(A \cap A') \subset f(A) \cap f(A')\), avec égalité si \(f\) est injective ;
\(f^{-1}(B \cup B') = f^{-1}(B) \cup f^{-1}(B')\) et \(f^{-1}(B \cap B') = f^{-1}(B) \cap f^{-1}(B')\) ;
\(A \subset f^{-1}(f(A))\) et \(f(f^{-1}(B)) \subset B\), avec égalité dans la première si \(f\) est injective et dans la seconde si \(f\) est surjective.

4. Composition et application réciproque

Composée

Si \(f : E \to F\) et \(g : F \to G\), la composée \(g \circ f : E \to G\) est définie par \((g \circ f)(x) = g(f(x))\). La composition est associative, mais en général \(g \circ f \neq f \circ g\).

Composition et injectivité, surjectivité

Si \(f\) et \(g\) sont injectives (resp. surjectives, bijectives), alors \(g \circ f\) l’est aussi.
Si \(g \circ f\) est injective, alors \(f\) est injective. Si \(g \circ f\) est surjective, alors \(g\) est surjective.

Preuve de la première réciproque. Si \(f(x) = f(x')\), alors \(g(f(x)) = g(f(x'))\), donc \(x = x'\) par injectivité de \(g \circ f\).

Application réciproque

Une application \(f : E \to F\) est bijective si et seulement s’il existe \(g : F \to E\) telle que \(g \circ f = \mathrm{id}_E\) et \(f \circ g = \mathrm{id}_F\). Cette application \(g\) est unique : c’est l’application réciproque \(f^{-1}\). On a alors \((g \circ f)^{-1} = f^{-1} \circ g^{-1}\) pour deux bijections composables.

Exemple 3

Soit \(f : \mathbb{R} \setminus \{1\} \to \mathbb{R} \setminus \{2\}\), \(f(x) = \dfrac{2x + 1}{x - 1}\). Pour \(y \neq 2\), l’équation \(y = \dfrac{2x + 1}{x - 1}\) équivaut à \(x(y - 2) = y + 1\), soit \(x = \dfrac{y + 1}{y - 2}\), qui est bien différent de \(1\). Il y a donc un unique antécédent : \(f\) est bijective et \(f^{-1}(y) = \dfrac{y + 1}{y - 2}\). Vérification : \(f(0) = -1\) et \(f^{-1}(-1) = 0\).

5. Ensembles finis et cardinal

Un ensemble est fini s’il est en bijection avec \(\{1, \dots, n\}\) pour un entier \(n\) ; ce nombre est son cardinal, noté \(|E|\) ou \(\mathrm{Card}(E)\). Le cardinal du vide est \(0\).

Règles de dénombrement

\(|A \cup B| = |A| + |B| - |A \cap B|\) ; si \(A \cap B = \varnothing\), c’est la somme (principe additif).
\(|A \times B| = |A| \times |B|\) (principe multiplicatif).
\(|\mathcal{P}(E)| = 2^n\) si \(|E| = n\).
Si \(|E| = n\) et \(|F| = p\), il y a \(p^n\) applications de \(E\) dans \(F\).
Si \(|E| = |F| < \infty\) : \(f : E \to F\) est injective \(\Leftrightarrow\) surjective \(\Leftrightarrow\) bijective.
Une injection de \(E\) dans \(F\) impose \(|E| \le |F|\), une surjection impose \(|E| \ge |F|\).

Astuce de Zyro

Pour compter, demande-toi toujours : est-ce que l’ordre compte ? est-ce que les répétitions sont permises ? Ces deux questions choisissent la bonne formule.

6. Arrangements et combinaisons

Arrangements, combinaisons

Soit \(E\) de cardinal \(n\) et \(0 \le p \le n\).

Un arrangement de \(p\) éléments de \(E\) est une liste ordonnée de \(p\) éléments distincts. Leur nombre est \(A_n^p = \dfrac{n!}{(n-p)!} = n(n-1)\cdots(n-p+1)\).
Une combinaison de \(p\) éléments est une partie de \(E\) à \(p\) éléments. Leur nombre est \(\dbinom{n}{p} = \dfrac{n!}{p!\,(n-p)!}\).

Comme chaque combinaison de \(p\) éléments se range de \(p!\) façons, \(A_n^p = p! \dbinom{n}{p}\). On a aussi \(\dbinom{n}{p} = \dbinom{n}{n-p}\) et la relation de Pascal \(\dbinom{n}{p} = \dbinom{n-1}{p-1} + \dbinom{n-1}{p}\) (on distingue les parties qui contiennent un élément fixé de celles qui ne le contiennent pas). Elle construit le triangle de Pascal.

n \ k	0	1	2	3	4	5	6
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1

Exemple 4

Dans un groupe de \(20\) étudiants, on choisit \(3\) délégués sans distinction de rôle : \(\dbinom{20}{3} = \dfrac{20 \times 19 \times 18}{6} = 1140\) possibilités. Si l’on désigne un président, un secrétaire et un trésorier, l’ordre compte : \(A_{20}^3 = 20 \times 19 \times 18 = 6840\), soit \(6 \times 1140\).

7. La formule du binôme

Formule du binôme de Newton

Pour des nombres \(a, b\) et un entier \(n \ge 0\) : \[ (a + b)^n = \sum_{k=0}^{n} \dbinom{n}{k} a^k b^{n-k}. \]

La raison est combinatoire : en développant le produit de \(n\) facteurs \((a + b)\), le terme \(a^k b^{n-k}\) apparaît autant de fois qu’il y a de façons de choisir les \(k\) facteurs qui fournissent \(a\), c’est-à-dire \(\dbinom{n}{k}\). Avec \(a = b = 1\), on obtient \(\sum_{k=0}^n \dbinom{n}{k} = 2^n\) ; avec \(a = 1\), \(b = -1\) et \(n \ge 1\), \(\sum_{k=0}^n (-1)^k \dbinom{n}{k} = 0\).

Exemple 5

Développons \((2x - 1)^5\). Avec \(a = 2x\) et \(b = -1\) : \[(2x - 1)^5 = 32x^5 - 80x^4 + 80x^3 - 40x^2 + 10x - 1.\] Test : pour \(x = 1\), la somme des coefficients vaut \(32 - 80 + 80 - 40 + 10 - 1 = 1 = 1^5\).

Erreur classique

\((a + b)^2\) n’est pas \(a^2 + b^2\) : il manque le terme \(2ab = \dbinom{2}{1} ab\). Pensez aussi aux signes quand \(b\) est négatif.

8. Le principe des tiroirs

Principe des tiroirs de Dirichlet

Si l’on range \(N\) objets dans \(n\) tiroirs avec \(N > n\), au moins un tiroir contient au moins deux objets. Plus précisément, un tiroir en contient au moins \(\left\lceil \dfrac{N}{n} \right\rceil\). De façon équivalente, il n’existe aucune injection d’un ensemble fini dans un ensemble strictement plus petit.

Exemple 6

On choisit \(6\) nombres dans \(\{1, 2, \dots, 10\}\). Montrons que deux d’entre eux ont pour somme \(11\). Formons les cinq paires \(\{1, 10\}, \{2, 9\}, \{3, 8\}, \{4, 7\}, \{5, 6\}\) : ce sont nos tiroirs. Six nombres dans cinq paires : deux nombres tombent dans la même paire, et leur somme est \(11\).

À retenir

Une application donne à chaque élément de départ une image et une seule ; injective = au plus un antécédent, surjective = au moins un, bijective = exactement un.
\(f(A)\) est une partie de l’arrivée, \(f^{-1}(B)\) une partie du départ ; l’image réciproque respecte unions et intersections, pas l’image directe pour \(\cap\).
Une bijection a une réciproque et \((g \circ f)^{-1} = f^{-1} \circ g^{-1}\).
\(|A \cup B| = |A| + |B| - |A \cap B|\), \(|A \times B| = |A||B|\), \(|\mathcal{P}(E)| = 2^n\), \(p^n\) applications.
\(A_n^p = \dfrac{n!}{(n-p)!}\) (ordre) et \(\dbinom{n}{p} = \dfrac{n!}{p!(n-p)!}\) (sans ordre) ; relation de Pascal.
\((a+b)^n = \sum \dbinom{n}{k} a^k b^{n-k}\) ; principe des tiroirs : \(N > n\) objets dans \(n\) tiroirs, une collision.