Soient $n,p\in\mathbb N^*$.
- Montrer que le nombre d'applications strictement croissantes de $\llbracket1,p\rrbracket$ dans $\llbracket1,n\rrbracket$ est $\binom np$.
- À une application croissante (au sens large) $f:\llbracket1,p\rrbracket\to\llbracket1,n\rrbracket$, on associe $g:\llbracket1,p\rrbracket\to\mathbb Z$ définie par $g(i)=f(i)+i-1$. Montrer que $f\mapsto g$ est une bijection de l'ensemble des applications croissantes de $\llbracket1,p\rrbracket$ dans $\llbracket1,n\rrbracket$ sur l'ensemble des applications strictement croissantes de $\llbracket1,p\rrbracket$ dans $\llbracket1,n+p-1\rrbracket$.
- En déduire le nombre d'applications croissantes de $\llbracket1,p\rrbracket$ dans $\llbracket1,n\rrbracket$. Contrôler pour $n=p=2$.
- On lance trois dés à six faces indiscernables ; un résultat est la donnée des trois valeurs obtenues, sans ordre, avec répétitions possibles. Combien y a-t-il de résultats ? Combien ont trois valeurs distinctes ?
Une application strictement croissante est déterminée par son image.
Pour des entiers, $g(i+1)>g(i)$ équivaut à $g(i+1)\ge g(i)+1$.
Ranger les trois valeurs des dés dans l'ordre croissant.
- Notons $\mathcal S$ l'ensemble des applications strictement croissantes de $\llbracket1,p\rrbracket$ dans $\llbracket1,n\rrbracket$ et $\Psi:\mathcal S\to\mathcal P_p(\llbracket1,n\rrbracket)$, $f\mapsto f(\llbracket1,p\rrbracket)$. Une application strictement croissante est injective, donc son image a $p$ éléments : $\Psi$ est bien définie.
- Surjectivité : si $A=\{a_1<\dots<a_p\}$, l'application $i\mapsto a_i$ est strictement croissante d'image $A$.
- Injectivité : si $f\in\mathcal S$ a pour image $A=\{a_1<\dots<a_p\}$, les nombres $f(1)<\dots<f(p)$ sont les éléments de $A$ rangés dans l'ordre croissant, donc $f(i)=a_i$ pour tout $i$ : $f$ est déterminée par son image. Donc $\operatorname{Card}\mathcal S=\binom np$ (ce nombre est nul si $p>n$).
- Soit $f$ croissante de $\llbracket1,p\rrbracket$ dans $\llbracket1,n\rrbracket$ et $g(i)=f(i)+i-1$. Pour $1\le i<p$, $g(i+1)-g(i)=f(i+1)-f(i)+1\ge1$ : $g$ est strictement croissante. De plus $g(1)=f(1)\ge1$ et $g(p)=f(p)+p-1\le n+p-1$ ; par croissance, $g$ est à valeurs dans $\llbracket1,n+p-1\rrbracket$.
Réciproquement, soit $g$ strictement croissante de $\llbracket1,p\rrbracket$ dans $\llbracket1,n+p-1\rrbracket$ et $f(i)=g(i)-i+1$. Les valeurs de $g$ étant entières, $g(i+1)\ge g(i)+1$, d'où $f(i+1)-f(i)=g(i+1)-g(i)-1\ge0$ : $f$ est croissante. De plus $f(1)=g(1)\ge1$ et $f(p)=g(p)-p+1\le n$, donc, par croissance, $f$ est à valeurs dans $\llbracket1,n\rrbracket$.
Les applications $f\mapsto g$ et $g\mapsto f$ sont réciproques l'une de l'autre : c'est une bijection.
- Par invariance du cardinal par bijection et par la question 1 appliquée avec $n+p-1$ à la place de $n$, le nombre d'applications croissantes de $\llbracket1,p\rrbracket$ dans $\llbracket1,n\rrbracket$ vaut $\binom{n+p-1}{p}$.
Contrôle pour $n=p=2$ : les applications croissantes sont $(1,1)$, $(1,2)$, $(2,2)$ (en notant $(f(1),f(2))$), soit $3=\binom32$.
- Un résultat se code de façon unique par ses trois valeurs rangées dans l'ordre croissant, $f(1)\le f(2)\le f(3)$ : c'est une application croissante de $\llbracket1,3\rrbracket$ dans $\llbracket1,6\rrbracket$, et réciproquement toute telle application code un résultat. Il y a donc $\binom{6+3-1}{3}=\binom83=56$ résultats. Ceux à trois valeurs distinctes correspondent aux applications strictement croissantes : $\binom63=20$.
$\binom np$ ; $\binom{n+p-1}{p}$ ; $56$ et $20$