Nombre de $p$-listes d'éléments distincts : énoncé (MPSI)
Nombre de $p$-listes d'éléments distincts
Soit $F$ de cardinal $n$ et $p\in\mathbb{N}^*$. Le nombre de $p$-listes d'éléments distincts de $F$ vaut $$n(n-1)\cdots(n-p+1)=\frac{n!}{(n-p)!}\quad\text{si }p\le n,$$ et $0$ si $p>n$.
Démonstration : Nombre de $p$-listes d'éléments distincts
Preuve
Notons $L_p$ l'ensemble de ces listes. Si $p>n$, $L_p=\varnothing$ par le principe des tiroirs. Supposons $p\le n$ et raisonnons par récurrence sur $p$.
Pour $p=1$ : $L_1$ est en bijection avec $F$, donc $\operatorname{Card}L_1=n$.
Soit $p<n$ tel que $\operatorname{Card}L_p=\frac{n!}{(n-p)!}$. L'application $$\pi:L_{p+1}\to L_p,\quad(y_1,\dots,y_{p+1})\mapsto(y_1,\dots,y_p)$$ est surjective, et chaque $(y_1,\dots,y_p)\in L_p$ a exactement $n-p$ antécédents : $y_{p+1}$ est un élément quelconque de $F\setminus\{y_1,\dots,y_p\}$, qui a $n-p$ éléments. Le lemme des bergers donne $$\operatorname{Card}L_{p+1}=(n-p)\frac{n!}{(n-p)!}=\frac{n!}{(n-p-1)!}.$$ Cela conclut la récurrence.
S’entraîner
- Applications et injections entre deux petits ensembles
- Mots de cinq lettres
- Délégués et comités
- Parties emboîtées
- Répartition en binômes