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 autre ${\displaystyle {\frac {1}{1-x}}}$, et donc la fonction génératrice finale est ${\displaystyle {\frac {1}{1-x}}{\frac {1}{1-x}}\dots {\frac {1}{1-x}}={\frac {1}{(1-x)^{k}}}}$

Pour déterminer le nombre de façon de placer n boules, on cherche le coefficient de ${\displaystyle x^{n}}$ (écrit ${\displaystyle [x^{n}]:}$) de cette fonction

${\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}}$.

Dans le cas où ${\displaystyle x_{i}>0}$, nous devons ajouter x au numérateur pour indiquer qu'au moins une boule est dans le bac, obtenant : ${\displaystyle {\frac {x}{1-x}}{\frac {x}{1-x}}\dots {\frac {x}{1-x}}={\frac {x^{k}}{(1-x)^{k}}}}$, 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 de un euro entre Arthur, Bernard et Charles 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 soit le multiensemble {a, b, b, b, d} soit 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-è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-è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ε.

Notes

1. (en) J Batterson, Competition Math for Middle School, Art of Problem Solving
2. (en) Philippe Flajolet et Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 26 juin 2009 (ISBN 978-0-521-89806-5)
3. (en) « Art of Problem Solving », sur artofproblemsolving.com (consulté le 26 octobre 2021)
4. (en) William Feller, An Introduction to Probability Theory and Its Applications, vol. 1, Wiley, 1968, 3rd éd., p. 38
5. (en) Paul Ehrenfest et Heike Kamerlingh Onnes, « Simplified deduction of the formula from the theory of combinations which Planck uses as the basis of his radiation theory », The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, vol. 29, n^o 170,‎ 1915, p. 297–301 (DOI 10.1080/14786440208635308, lire en ligne, consulté le 5 décembre 2020)
6. (de) Max Planck, « Ueber das Gesetz der Energieverteilung im Normalspectrum », Annalen der Physik, vol. 309, n^o 3,‎ 1901, p. 553–563 (DOI 10.1002/andp.19013090310 , Bibcode 1901AnP...309..553P)
7. (en) C. Gearhart, « Planck, the Quantum, and the Historians », Phys. perspect., vol. 4,‎ 2002, p. 170–215 (DOI 10.1007/s00016-002-8363-7, lire en ligne, consulté le 16 mai 2024)

Voir aussi

Articles connexes

• Partition d'un entier
• Coefficient binomial de Gauss

Bibliographie

(en) Jim Pitman, Probability, Berlin, Springer-Verlag, 1993 (ISBN 0-387-97974-3)

Liens externes

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Stars and bars (combinatorics) » (voir la liste des auteurs).

• (en) Eric W. Weisstein, « Multichoose », sur Mathworld -- A Wolfram Web Resource (consulté le 18 novembre 2012)