Prépa, 1re année › Dénombrement › Injections et permutations

Injections et permutations : énoncé (MPSI)

Propriété

Injections et permutations

Soient $E$ de cardinal $p$ et $F$ de cardinal $n$.

Le nombre d'injections de $E$ dans $F$ vaut $\frac{n!}{(n-p)!}$ si $p\le n$, et $0$ si $p>n$.
Le nombre de bijections de $E$ sur $F$ vaut $n!$ si $p=n$.
En particulier, le groupe symétrique $\mathfrak{S}_n$ des permutations de $\llbracket1,n\rrbracket$ a $n!$ éléments.

Preuve : avec $E=\{x_1,\dots,x_p\}$, la bijection $f\mapsto(f(x_1),\dots,f(x_p))$ envoie les injections exactement sur les $p$-listes d'éléments distincts. Pour $p=n$, une injection est une bijection (même cardinal), et $\frac{n!}{0!}=n!$.

Exemple

Applications chiffrées

Tiercé dans l'ordre avec $16$ chevaux : $16\times15\times14=3360$ arrivées possibles (3-listes d'éléments distincts).
Codes à $4$ chiffres tous distincts : $10\times9\times8\times7=5040$.
Injections de $\llbracket1,3\rrbracket$ dans $\llbracket1,5\rrbracket$ : $5\times4\times3=60$, parmi les $5^3=125$ applications.
Surjections de $\llbracket1,3\rrbracket$ sur $\{a,b\}$ : parmi les $2^3=8$ applications, seules les $2$ applications constantes ne sont pas surjectives, d'où $6$ surjections.
Façons d'asseoir $6$ personnes sur $6$ chaises numérotées : $6!=720$.

Remarque

Notation $A_n^p$

Le nombre $\frac{n!}{(n-p)!}$ est parfois noté $A_n^p$ (nombre d'arrangements). Cette notation n'est pas celle du programme : on peut l'utiliser à condition de la définir dans la copie.

S’entraîner

Dans le cours

Dénombrement : Injections et permutations