Méthode des étoiles et des barres

En combinatoire, la méthode des étoiles et des barres, stars and bars method en anglais, (également appelée méthode des bâtons et des pierres^[1], des ronds et des barres^[2], ou des points et des séparateurs^[3]) est une méthode graphique permettant de résoudre plusieurs problèmes de dénombrement simples, comme la détermination du nombre de façons de mettre n boules indiscernables dans k bacs discernables^[4].

Énoncés des théorèmes

La méthode des étoiles et des barres est souvent introduite spécifiquement pour prouver les deux théorèmes suivants de combinatoire élémentaire concernant le nombre de solutions à une équation diophantienne.

Premier théorème

Pour tout couple d'entiers strictement positifs n et k, le nombre de k-uplets d'entiers strictement positifs dont la somme vaut n, c'est-à-dire le nombre de compositions de n, est égal au nombre de parties à (k − 1) éléments d'un ensemble à n − 1 éléments. Par exemple, si n = 10 et k = 4, le théorème montre que le nombre de solutions de x₁ + x₂ + x₃ + x₄ = 10 (avec x₁, x₂, x₃, x₄ > 0) est égal au coefficient binomial :${\displaystyle {\binom {n-1}{k-1}}={\binom {10-1}{4-1}}={\binom {9}{3}}=84.}$

Deuxième théorème

Pour tout couple d'entiers strictement positifs n et k, le nombre de k-uplets d'entiers positifs ou nuls dont la somme vaut n est égal au nombre de multiensembles de cardinal n inclus dans un ensemble de taille k, ou le nombre de n-combinaisons avec répétitions de k objets, soit ${\displaystyle \Gamma _{k}^{n}=\left(\!\!{k \choose n}\!\!\right)={k+n-1 \choose n}}$ . De façon équivalente, c'est aussi le nombre de multiensembles de cardinal k − 1 pris dans un ensemble de taille n + 1.

Par exemple, si n = 10 et k = 4, le théorème donne le nombre de solutions de x₁ + x₂ + x₃ + x₄ = 10 (avec x₁, x₂, x₃, x₄ ${\displaystyle \geq 0}$ ) comme étant égal à :${\displaystyle \left(\!\!{k \choose n}\!\!\right)={k+n-1 \choose n}={\binom {13}{10}}=286}$, ou ${\displaystyle \left(\!\!{n+1 \choose k-1}\!\!\right)={n+1+k-1-1 \choose k-1}={\binom {13}{3}}=286}$, (cela correspond aux compositions faibles d'un entier).

Démonstrations par la méthode des étoiles et des barres

Preuve du premier théorème

Supposons qu'il y ait n objets (représentés ici par des étoiles) à placer dans k bacs, de sorte que tous les bacs contiennent au moins un objet. Les bacs sont discernables (disons qu'ils sont numérotés de 1 à k) mais les n étoiles ne le sont pas (donc les configurations ne sont distinguées que par le nombre d'étoiles présentes dans chaque bac). Une configuration est ainsi représentée par un k-uplet d'entiers strictement positifs, comme dans l'énoncé du théorème. Par exemple, avec n = 7 et k = 3, on commence par placer les étoiles en ligne ★ :

★★★★★★★

Fig. 1: Sept objets, représentés par des étoiles

La configuration sera déterminée dès que l'on connaitra la première étoile allant dans le deuxième bac, la première étoile allant dans le troisième bac, etc. Cela est indiqué en plaçant k − 1 barres entre les étoiles. Puisqu'aucun bac n'est autorisé à être vide (toutes les variables sont strictement positives), il y a au plus une barre entre chaque paire d'étoiles. Par exemple  :

★★★★|★|★★

Fig. 2: Ces deux barres donnent naissance à trois bacs contenant 4, 1 et 2 objets

Il y a n − 1 espaces entre les étoiles. Une configuration est obtenue en choisissant k − 1 de ces espaces pour contenir une barre ; il y a donc ${\displaystyle {\tbinom {n-1}{k-1}}}$ combinaisons possibles.

Preuve du deuxième théorème

Dans ce cas, accepter qu'un bac soit vide signifie que nous pouvons placer plusieurs barres entre des étoiles, avant la première étoile et après la dernière étoile. Par exemple, lorsque n = 7 et k = 5, le 5-uplet (4, 0, 1, 2, 0) peut être représenté par le diagramme suivant :

★★★★| |★|★★|

Fig. 3: Ces quatre barres donnent naissance à cinq bacs contenant 4, 0, 1, 2 et 0 objets

Pour voir qu'il y a ${\displaystyle {\tbinom {n+k-1}{k-1}}}$ configurations possibles, on remarque que toute configuration d'étoiles et de barres se compose d'un total de n + k − 1 objets, dont ${\displaystyle n}$ étoiles et k − 1 barres. Ainsi, nous avons seulement besoin de choisir k − 1 des n + k − 1 positions pour être des barres (ou, équivalemment, choisir ${\displaystyle n}$ des positions pour être des étoiles). Le théorème 1 peut maintenant être reformulé dans les termes du théorème 2, car l'exigence que toutes les variables soient strictement positives équivaut à attribuer à chaque variable un 1 au préalable, et à demander le nombre de solutions lorsque chaque variable est positive ou nulle. Par exemple :

${\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=10}$ avec ${\displaystyle x_{1},x_{2},x_{3},x_{4}>0}$

est équivalent à :

${\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=6}$ avec ${\displaystyle x_{1},x_{2},x_{3},x_{4}\geqslant 0}$

Démonstrations à l'aide de fonctions génératrices

Les deux cas sont très similaires. Dans le cas où ${\displaystyle x_{i}\geqslant 0}$, chaque bac est représenté par la série génératrice ${\displaystyle 1+x+x^{2}+\dots ={\frac {1}{1-x}}}$, où l'exposant de x nous indique combien de boules sont placées dans le bac. Chaque bac supplémentaire est représenté par un facteur ${\displaystyle {\frac {1}{1-x}}}$, et donc la fonction génératrice finale est ${\displaystyle {\frac {1}{1-x}}{\frac {1}{1-x}}\cdots {\frac {1}{1-x}}={\frac {1}{(1-x)^{k}}}}$.

(Plus formellement, un terme du développement du produit

${\displaystyle (1+x+x^{2}+\cdots )(1+x+x^{2}+\cdots )\cdots (1+x+x^{2}+\cdots )}$

est déterminé par le choix d'un terme ${\displaystyle x^{m_{i}}}$ dans le i-ème facteur, pour chaque i entre 1 et k et le monôme correspondant est de degré ${\displaystyle m_{1}+\cdots +m_{k}}$. Autrement dit chaque composition de n contribue pour 1 au terme de degré n de la série génératrice.)

Pour déterminer le nombre de façon de placer n boules, on cherche donc le coefficient de ${\displaystyle x^{n}}$ de cette série, qui est noté

${\displaystyle [x^{n}]{\frac {1}{(1-x)^{k}}}}$.

La série de Taylor de cette fonction (obtenue en dérivant k fois la série ${\displaystyle {\frac {1}{1-x}}}$) est ${\displaystyle \sum _{n=0}^{\infty }{\binom {n+k-1}{k-1}}x^{n}}$, ce qui permet de conclure.

Dans le cas où ${\displaystyle x_{i}>0}$, on multiplie la série associée à chaque bac par x pour indiquer qu'il contient au moins une boule, ce qui donne : ${\displaystyle {\frac {x}{1-x}}{\frac {x}{1-x}}\cdots {\frac {x}{1-x}}={\frac {x^{k}}{(1-x)^{k}}}}$, le facteur ${\displaystyle x^{k}}$ au numérateur produit simplement un décalage d'indices et le coefficient de ${\displaystyle x^{n}}$ est alors ${\displaystyle {\binom {n-1}{k-1}}}$.

Exemples

Quatre cookies sont distribués entre Tom, Dick et Harry (TDH) de telle manière que chacun obtienne au moins un cookie. Les 4 cookies sont traditionnellement représentés par des étoiles (****), mais ici ils sont montrés comme des cercles colorés comme des cookies (●●●●). Les 3 espaces entre les cookies sont indiqués par des carets rouges (^ ^ ^). Avec trois personnes, nous avons besoin de 2 barres (| |) pour occuper deux des trois espaces. Ainsi, le problème se réduit à trouver le coefficient binomial ${\displaystyle {\tbinom {3}{2}}.}$ Sont également montrées les trois 3-compositions de 4.

Les deux versions du problème, selon qu'un bac est autorisé à avoir zéro élément ou non. Dans les deux cas, le nombre de bacs est 3. Si zéro n'est pas autorisé, le nombre de cookies est n = 6. Si zéro est autorisé, le nombre de cookies n'est que de n = 3, comme décrit dans la figure précédente.

Exemple 1

De nombreux problèmes de dénombrement simples (souvent proposés dans l'enseignement primaire) sont résolus par les théorèmes ci-dessus. Par exemple, si l'on souhaite compter le nombre de façons de distribuer sept pièces d'un euro entre Alice, Bob et Ève de sorte que chacun reçoive au moins un euro, cela revient à appliquer le premier théorème avec n = 7 et k = 3, et il y a ${\displaystyle {\tbinom {7-1}{3-1}}=15}$ façons de distribuer les pièces.

Exemple 2

Si n = 5, k = 4, l'ensemble de taille k étant {a, b, c, d}, alors ★|★★★||★ pourrait représenter le multiensemble {a, b, b, b, d} ou le 4-uplet (1, 3, 0, 1). Cette représentation avec n = 5 étoiles et k – 1 = 3 barres montre donc qu'il y a ${\displaystyle {\tbinom {5+4-1}{4-1}}={\tbinom {8}{3}}=56}$ multiensembles de cette forme.

La possibilité de bacs vides permet d'avoir plus de barres que d'étoiles, ce qui n'est pas permis dans les cas couverts par le premier théorème. Ainsi, par exemple, on ne peut mettre 7 boules dans 10 bacs sans en laisser de vides (c'est l'inverse du principe des tiroirs), mais il y a ${\displaystyle {\tbinom {16}{9}}=11440}$ répartitions possibles de ces sept boules si on accepte les vides.

Exemple 3

Nous pouvons utiliser cette méthode pour calculer le produit de Cauchy de m copies de la série entière ${\displaystyle \sum _{k=1}^{\infty }x^{k}={\frac {x}{1-x}}}$ : pour le n-ième terme de ce développement, nous choisissons n puissances de x parmi m emplacements séparés. Il y a donc ${\displaystyle {\tbinom {n-1}{m-1}}}$ façons de former cette n-ième puissance et ${\displaystyle \left[\sum _{k=1}^{\infty }x^{k}\right]^{m}=\sum _{n=m}^{\infty }{{n-1} \choose {m-1}}x^{n}}$.

Exemple 4

La méthode graphique a été utilisée par Paul Ehrenfest et Heike Kamerlingh Onnes — avec le symbole ε (élément d'énergie quantique) à la place d'une étoile et le symbole 0 à la place d'une barre — comme une dérivation simple de l'expression de Max Planck pour le nombre de complexions pour un système de résonateurs d'une fréquence unique^[5]. Par complexions (micro-états), Planck entendait la distribution des P éléments d'énergie ε sur N résonateurs^[6],[7]. Le nombre R de complexions est ${\displaystyle R={\frac {(N+P-1)!}{P!(N-1)!}}.\ }$ La représentation graphique de chaque distribution possible contiendrait P copies du symbole ε et N – 1 copies du symbole 0. Dans leur démonstration, Ehrenfest et Kamerlingh Onnes ont pris N = 4 et P = 7 (c'est-à-dire R = 120 combinaisons), et ils ont choisi le 4-uplet (4, 2, 0, 1) comme exemple illustratif pour cette représentation symbolique : εεεε0εε00ε.