Exercice 110

Idée. Le produit $i_{1} \cdots i_{p}$ compte les façons de marquer un objet dans chacun de $p$ blocs consécutifs de tailles $i_{1}$, …, $i_{p}$. On code un découpage de $n$ objets alignés, avec un objet marqué par bloc, en insérant $p - 1$ cases séparatrices : on obtient une rangée de $n + p - 1$ cases, dans laquelle les $p$ cases marquées et les $p - 1$ séparateurs forment $2p - 1$ cases qui alternent.

Les configurations. Si l'un des $i_{k}$ est nul, le produit est nul : la somme porte en fait sur les $p$-uplets d'entiers $i_{k} \geqslant 1$ de somme $n$. Pour un tel $p$-uplet, le produit $i_{1} \cdots i_{p}$ est le nombre de $p$-uplets $(j_{1}, \dots, j_{p})$ tels que $1 \leqslant j_{k} \leqslant i_{k}$ (proposition 2 (iv)). Le membre de gauche est donc le cardinal de l'ensemble $\mathcal{C}$ des configurations $\big((i_{k}), (j_{k})\big)$, avec $i_{k} \geqslant 1$, $\sum i_{k} = n$ et $1 \leqslant j_{k} \leqslant i_{k}$ : on range $n$ objets en $p$ blocs consécutifs non vides de tailles $i_{1}$, …, $i_{p}$, et l'on marque l'objet de rang $j_{k}$ dans le bloc $k$.

Le codage. On note $I_{k} = i_{1} + \cdots + i_{k}$, avec $I_{0} = 0$, et l'on associe à une configuration les entiers $$c_{2k-1} = I_{k-1} + (k - 1) + j_{k} \quad (1 \leqslant k \leqslant p), \qquad c_{2k} = I_{k} + k \quad (1 \leqslant k \leqslant p - 1).$$ Dans la rangée de $n + p - 1$ cases, où l'on a inséré une case séparatrice après chacun des $p - 1$ premiers blocs, $c_{2k}$ est la position du $k$-ième séparateur et $c_{2k-1}$ celle de l'objet marqué du bloc $k$. On a $1 \leqslant c_{1} = j_{1}$, $c_{2p-1} \leqslant I_{p} + p - 1 = n + p - 1$, et la suite est strictement croissante : $$c_{2k-1} \leqslant I_{k} + k - 1 < I_{k} + k = c_{2k}, \qquad c_{2k} = I_{k} + k < I_{k} + k + j_{k+1} = c_{2k+1}.$$ On définit ainsi une application $\Phi$ de $\mathcal{C}$ dans l'ensemble des parties à $2p - 1$ éléments de $\llbracket 1\,,n + p - 1 \rrbracket$.

La réciproque. Soit $c_{1} < \cdots < c_{2p-1}$ des éléments de $\llbracket 1\,,n + p - 1 \rrbracket$, et $c_{0} = 0$, $c_{2p} = n + p$. On pose $$i_{k} = c_{2k} - c_{2k-2} - 1, \qquad j_{k} = c_{2k-1} - c_{2k-2} \qquad (1 \leqslant k \leqslant p).$$ Comme $c_{2k} - c_{2k-2} \geqslant 2$, on a $i_{k} \geqslant 1$ ; on a aussi $1 \leqslant j_{k} \leqslant c_{2k} - 1 - c_{2k-2} = i_{k}$, et la somme télescopique donne $\sum i_{k} = c_{2p} - c_{0} - p = n$. On obtient une configuration, et l'on vérifie que les deux constructions sont réciproques l'une de l'autre : partant d'une configuration, $c_{2k} - c_{2k-2} - 1 = i_{k}$ et $c_{2k-1} - c_{2k-2} = j_{k}$ ; partant des $c$, on retrouve $I_{k} + k = c_{2k}$ en sommant, puis $c_{2k-1}$. L'application $\Phi$ est une bijection (chapitre 2), et le théorème 2 donne $$\boxed{\sum_{\substack{(i_{1}, \dots, i_{p}) \in \mathbb{N}^{p} \\ i_{1} + \cdots + i_{p} = n}} i_{1}i_{2}\cdots i_{p} = |\mathcal{C}| = \binom{n + p - 1}{2p - 1}}$$ avec la convention $\binom{n + p - 1}{2p - 1} = 0$ lorsque $p > n$ : les deux membres sont alors nuls, puisque $p$ blocs non vides demandent au moins $p$ objets.

Pour $n = 7$ et $p = 3$, la configuration formée des blocs de tailles $(2, 3, 2)$ et des rangs marqués $(2, 1, 2)$ est codée par les cases $\{2, 3, 4, 7, 9\}$ parmi $9$ : les séparateurs, en bleu, occupent les cases $3$ et $7$, et les objets marqués, en ocre plein, les cases $2$, $4$ et $9$. Pour $n = 4$ et $p = 2$, on trouve $0 \times 4 + 1 \times 3 + 2 \times 2 + 3 \times 1 + 4 \times 0 = 10 = \binom{5}{3}$, et l'identité a été vérifiée pour $n \leqslant 10$ et $p \leqslant 5$, ainsi que la bijection pour quelques couples $(n, p)$ ✓.

À retenir. Pour $p = 2$, on obtient $\sum_{i=0}^{n} i(n - i) = \binom{n + 1}{3}$, que l'on retrouve par le calcul avec les sommes du chapitre 3. Ranger des objets et des séparateurs dans une même rangée est aussi la façon de compter les $p$-uplets d'entiers naturels de somme $n$, au nombre de $\binom{n + p - 1}{n}$ : c'est la case hors programme du tableau de la section 21.2.6, où l'on choisit $n$ éléments parmi $p$, avec répétitions et sans ordre.