Des étoiles et des barres

Stratégie : encoder — l'arme secrète du dénombrement. Les solutions d'une équation sont difficiles à compter directement. On leur fait correspondre des mots, que l'on sait compter, et on vérifie que la correspondance est une bijection.

1) Le codage. À une solution $(x_1,\dots ,x_p)$ associons un mot formé de $n$ étoiles et de $p-1$ barres : on écrit $x_1$ étoiles, une barre, $x_2$ étoiles, une barre, et ainsi de suite jusqu'à $x_p$ étoiles. Par exemple, pour $p=3$ et $n=5$, la solution $(2,0,3)$ devient

$$\star \star \mid \mid \star \star \star$$

2) C'est une bijection. Réciproquement, tout mot composé de $n$ étoiles et de $p-1$ barres se relit comme une solution : $x_i$ est le nombre d'étoiles situées dans le $i$-ième bloc, entre la barre numéro $i-1$ et la barre numéro $i$. Les deux constructions sont inverses l'une de l'autre, et la somme des $x_i$ vaut bien le nombre total d'étoiles, c'est-à-dire $n$.

3) Le comptage des mots. Un tel mot compte $n+p-1$ symboles en tout ; il est entièrement déterminé par le choix des positions des $p-1$ barres parmi ces $n+p-1$ places. D'où

$$\boxed{\left(\genfrac{}{}{0ex}{}{n+p-1}{p-1}\right)=\left(\genfrac{}{}{0ex}{}{n+p-1}{n}\right)\text{solutions.}}$$

⚠️ Deux points délicats, tous deux dans le codage. D'abord, il y a $p-1$ barres et non $p$ : avec $p$ blocs, il ne faut que $p-1$ séparateurs. Ensuite, les blocs vides sont autorisés, ce qui correspond à deux barres consécutives, ou à une barre en début ou en fin de mot : c'est exactement ce qui traduit l'autorisation $x_i=0$. Si l'énoncé imposait $x_i\ge 1$, il faudrait interdire les blocs vides — les barres devraient alors se glisser dans les $n-1$ intervalles séparant deux étoiles, et le compte deviendrait $\left(\genfrac{}{}{0ex}{}{n-1}{p-1}\right)$.

Contrôle par énumération complète, avec $p=3$ et $n=2$. La formule annonce $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$. Écrivons toutes les solutions de $x_1+x_2+x_3=2$ : $(2,0,0)$, $(0,2,0)$, $(0,0,2)$, $(1,1,0)$, $(1,0,1)$ et $(0,1,1)$. Elles sont bien six ✓. Un balayage informatique confirme la formule pour tous les couples avec $p\le 5$ et $n\le 8$ ✓.

Second contrôle, immédiat. Pour $p=2$, la formule donne $\left(\genfrac{}{}{0ex}{}{n+1}{1}\right)=n+1$, et l'équation $x_1+x_2=n$ a effectivement $n+1$ solutions, obtenues en faisant courir $x_1$ de $0$ à $n$ ✓.

Ce que l'exercice installe. Ce dénombrement remplit la case manquante du tableau du cours. Les listes ordonnées avec répétition se comptent par $n^p$, celles sans répétition par $\frac{n!}{(n-p)!}$, les parties par $\left(\genfrac{}{}{0ex}{}{n}{p}\right)$ — et la quatrième case, les tirages simultanés avec remise, c'est celle-ci : choisir $p$ objets parmi $n$ sans tenir compte de l'ordre mais en autorisant les répétitions revient à répartir $p$ unités entre $n$ catégories, soit $\left(\genfrac{}{}{0ex}{}{n+p-1}{p}\right)$ façons.