Nombre de k-uplets d'éléments distincts : énoncé (Terminale spé)

On note $A_k$ le nombre de k-uplets d'éléments distincts de $E$, pour $1\leqslant k\leqslant n$. Montrons par récurrence finie que $A_k=n(n-1)\cdots(n-k+1)$.

Initialisation. Pour $k=1$, un 1-uplet $(x_1)$ est toujours à éléments distincts : $A_1=n$.

Hérédité. Soit $k$ avec $1\leqslant k\leqslant n-1$ et $A_k=n(n-1)\cdots(n-k+1)$. Un $(k+1)$-uplet d'éléments distincts s'obtient de façon unique en choisissant d'abord un k-uplet d'éléments distincts $(x_1;\ldots;x_k)$, puis un élément $x_{k+1}$ différent de $x_1,\ldots,x_k$. Quel que soit le k-uplet choisi, il reste exactement $n-k$ choix pour $x_{k+1}$. Par le principe multiplicatif : $$A_{k+1}=A_k\times(n-k)=n(n-1)\cdots(n-k+1)(n-k).$$ C'est la formule au rang $k+1$.

Écriture avec les factorielles. $$n(n-1)\cdots(n-k+1)=\frac{n(n-1)\cdots(n-k+1)\times(n-k)\times\cdots\times1}{(n-k)\times\cdots\times1}=\frac{n!}{(n-k)!}.$$ Pour $k=n$, le dénominateur vaut $0!=1$, ce qui justifie la convention.