Exercice 12

1. Une application strictement croissante $f : \llbracket 1\,,p \rrbracket \to \llbracket 1\,,n \rrbracket$ est injective, et son image $f\big(\llbracket 1\,,p \rrbracket\big)$ est une partie à $p$ éléments de $\llbracket 1\,,n \rrbracket$. Réciproquement, une partie à $p$ éléments $\{y_{1} < \cdots < y_{p}\}$ est l'image d'une unique application strictement croissante, $k \mapsto y_{k}$ : les valeurs d'une telle application sont nécessairement les éléments de son image rangés dans l'ordre croissant. L'application $f \mapsto f\big(\llbracket 1\,,p \rrbracket\big)$ est donc une bijection, et le théorème 2 donne $$\boxed{\binom{n}{p} \text{ applications strictement croissantes de } \llbracket 1\,,p \rrbracket \text{ dans } \llbracket 1\,,n \rrbracket}$$ Ce nombre est nul si $p > n$, ce qui est cohérent : il n'y a alors aucune injection (théorème 1).

2. Notons $\mathcal{C}$ l'ensemble des applications croissantes de $\llbracket 1\,,p \rrbracket$ dans $\llbracket 1\,,n \rrbracket$, et $\mathcal{S}$ celui des applications strictement croissantes de $\llbracket 1\,,p \rrbracket$ dans $\llbracket 1\,,n + p - 1 \rrbracket$.

$\triangleright$ $\varphi$ est à valeurs dans $\mathcal{S}$. Soit $f \in \mathcal{C}$ et $k \in \llbracket 1\,,p \rrbracket$. On a $1 \leqslant f(k) \leqslant f(k) + k - 1 \leqslant n + p - 1$, et, pour $k \leqslant p - 1$, $$\varphi(f)(k + 1) = f(k + 1) + k \geqslant f(k) + k > f(k) + k - 1 = \varphi(f)(k).$$

$\triangleright$ Une réciproque. Pour $g \in \mathcal{S}$, on pose $\psi(g)(k) = g(k) - k + 1$. Comme $g$ est strictement croissante et à valeurs entières, $g(k + 1) \geqslant g(k) + 1$, donc $\psi(g)(k + 1) = g(k + 1) - k \geqslant g(k) - k + 1 = \psi(g)(k)$ : $\psi(g)$ est croissante. Par récurrence, $g(k) \geqslant g(1) + (k - 1) \geqslant k$, et de même $g(k) \leqslant g(p) - (p - k) \leqslant n + k - 1$ ; ainsi $\psi(g)(k) \in \llbracket 1\,,n \rrbracket$, et $\psi(g) \in \mathcal{C}$. Enfin $\psi \circ \varphi$ et $\varphi \circ \psi$ sont les identités, puisque l'on ajoute puis retranche $k - 1$. Par le chapitre 2, théorème 1, $\varphi$ est une bijection de $\mathcal{C}$ sur $\mathcal{S}$.

La question 1, appliquée avec $n + p - 1$ au lieu de $n$, donne $$\boxed{|\mathcal{C}| = |\mathcal{S}| = \binom{n + p - 1}{p}}$$ Pour $n = 2$ et $p = 2$, on trouve $\binom{3}{2} = 3$ : ce sont les applications de valeurs $(1, 1)$, $(1, 2)$ et $(2, 2)$ ✓.

L'exercice 46 de la feuille du chapitre 3 a dénombré les $p$-uplets d'entiers naturels de somme $n$ : il y en a $\binom{n + p - 1}{p - 1}$. Une application croissante $f$ est déterminée par les nombres $x_{j} = \big|f^{-1}(\{j\})\big|$ de fois qu'elle prend chaque valeur $j \in \llbracket 1\,,n \rrbracket$ : c'est un $n$-uplet d'entiers naturels de somme $p$, et l'on retrouve, en échangeant les rôles de $n$ et $p$, le nombre $\binom{p + n - 1}{n - 1} = \binom{n + p - 1}{p}$ ✓. C'est le nombre « hors programme » du tableau de la section 21.2.6 : choisir $p$ éléments parmi $n$, sans ordre et avec répétitions, c'est choisir les valeurs d'une application croissante.

Piège. L'erreur la plus répandue est de croire qu'une application croissante est déterminée par son image, comme à la question 1 : les valeurs répétées sont perdues. Le décalage $k - 1$ de $\varphi$ sert précisément à séparer les valeurs égales, pour se ramener au cas strict.