Les étoiles et les barres

La stratégie. On ne compte pas les solutions, on les dessine : à chaque solution on associe un mot, et compter des mots, c'est choisir des positions — le geste des chemins de la grille, poussé là où il compte vraiment.

a) Le codage. À une solution $(x_1,\dots ,x_p)$ on associe le mot formé de $x_1$ étoiles, puis une barre, puis $x_2$ étoiles, puis une barre, et ainsi de suite jusqu'aux $x_p$ étoiles finales : $$\underset{x_1}{\underbrace{\star \cdots \star }}\mid \underset{x_2}{\underbrace{\star \cdots \star }}\mid \cdots \mid \underset{x_p}{\underbrace{\star \cdots \star }}.$$ Ce mot compte $n$ étoiles au total, puisque $x_1+\cdots +x_p=n$, et $p-1$ barres : il est de longueur $n+p-1$. Par exemple, pour $p=3$ et $n=5$, la solution $(2,0,3)$ s'écrit $\star \star \mid \mid \star \star \star$ — deux barres consécutives codent le zéro.

C'est une bijection. Réciproquement, tout mot de $n$ étoiles et $p-1$ barres se relit d'une unique façon : $x_i$ est le nombre d'étoiles entre la $(i-1)$-ième barre et la $i$-ième (avant la première pour $x_1$, après la dernière pour $x_p$), et ces nombres sont des entiers naturels de somme $n$. Le codage et le décodage sont inverses l'un de l'autre.

Le compte. Un tel mot est déterminé par les positions de ses $p-1$ barres parmi les $n+p-1$ places, les étoiles occupant le reste : $$\mathrm{card}\{(x_1,\dots ,x_p)\in {\mathbb{N}}^p\mid x_1+\cdots +x_p=n\}=\left(\genfrac{}{}{0ex}{}{n+p-1}{p-1}\right)=\left(\genfrac{}{}{0ex}{}{n+p-1}{n}\right).$$

Le point délicat. Les $x_i$ peuvent être nuls, et c'est ce qui fait marcher le codage : deux barres consécutives, une barre en tête ou en queue, codent exactement un $x_i=0$. Si l'on interdisait les blocs vides, la lecture ne serait plus surjective sur les mots.

b) Le cas $x_i\ge 1$. Le changement de variable $y_i=x_i-1$ est une bijection entre les solutions à coordonnées $\ge 1$ de $x_1+\cdots +x_p=n$ et les solutions dans ${\mathbb{N}}^p$ de $y_1+\cdots +y_p=n-p$. D'après a), il y en a $$\left(\genfrac{}{}{0ex}{}{(n-p)+p-1}{p-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{p-1}\right),$$ nombre nul si $n<p$, ce qui est correct : $p$ entiers au moins égaux à $1$ ont une somme au moins égale à $p$. On peut aussi le voir directement sur le dessin : les $n$ étoiles étant alignées, il s'agit de placer $p-1$ barres dans les $n-1$ intervalles entre deux étoiles consécutives, sans en mettre deux au même endroit — $\left(\genfrac{}{}{0ex}{}{n-1}{p-1}\right)$ choix.

Contrôle. $p=3$, $n=5$ : $\left(\genfrac{}{}{0ex}{}{7}{2}\right)=21$ solutions, et $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ à coordonnées $\ge 1$, à savoir les permutations de $(1,1,3)$ et de $(1,2,2)$ : $3+3=6$. $p=2$, $n=3$ : $\left(\genfrac{}{}{0ex}{}{4}{1}\right)=4$ solutions, $(0,3),(1,2),(2,1),(3,0)$.

Ce que l'exercice installe. Encoder : un objet difficile à compter se traduit en un mot, et un mot à deux lettres se compte en choisissant les positions d'une lettre. Le même nombre $\left(\genfrac{}{}{0ex}{}{n+p-1}{n}\right)$ compte les façons de ranger $n$ boules indiscernables dans $p$ boîtes, les monômes de degré $n$ en $p$ variables, et il apparaît au chapitre 17 comme coefficient de $z^n$ dans $\frac{1}{(1-z{)}^p}$. Une variante utile : les solutions de $x_1+\cdots +x_p\le n$ sont celles de $x_1+\cdots +x_p+x_{p+1}=n$ avec une variable d'écart, soit $\left(\genfrac{}{}{0ex}{}{n+p}{p}\right)$.