Méthode des étoiles et des barres

En combinatoire, la méthode des étoiles et des barres (également appelée bâtons et pierres^[1], boules et barres^[2], et points et séparateurs^[3]) est une méthode graphique pour dériver certains théorèmes. Elle peut être utilisée pour résoudre de nombreux problèmes de dénombrement simples, comme le nombre de façons de mettre $n$ boules indiscernables dans $k$ bacs discernables^[4].

Énoncés des théorèmes[modifier | modifier le code]

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

Premier théorème[modifier | modifier le code]

Pour toute paire d'entiers positifs $n$ et $k$ , le nombre de $k$ -uplets d'entiers positifs dont la somme vaut $n$ , c'est-à-dire le nombre de compositions de $n$ , est égal au nombre de sous-ensembles de $(k - 1)$ éléments d'un ensemble de $n - 1$ éléments. Par exemple, si $n = 10$ et $k = 4$ , le théorème donne le nombre de solutions de $x 1 + x 2 + x 3 + x 4 = 10$ (avec $x 1, x 2, x 3, x 4 > 0$ ) comme le coefficient binomial : ${\binom {n-1}{k-1}}={\binom {10-1}{4-1}}={\binom {9}{3}}=84.$

Deuxième théorème[modifier | modifier le code]

Pour toute paire d'entiers positifs $n$ et $k$ , le nombre de $k$ -uplets d'entiers non négatifs dont la somme vaut $n$ est égal au nombre de multiensembles de cardinal $n$ pris dans un ensemble de taille $k$ , ou équivalemment, 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 1 + x 2 + x 3 + x 4 = 10$ (avec $\geq 0$ ) comme : $\left(\!\!{k \choose n}\!\!\right)={k+n-1 \choose n}={\binom {13}{10}}=286$ , $\left(\!\!{n+1 \choose k-1}\!\!\right)={n+1+k-1-1 \choose k-1}={\binom {13}{3}}=286$ , ou encore ${\binom {n+k-1}{k-1}}={\binom {10+4-1}{4-1}}={\binom {13}{3}}=286$ (cela correspond aux compositions faibles d'un entier).

Démonstrations par la méthode des étoiles et des barres[modifier | modifier le code]

Preuve du premier théorème[modifier | modifier le code]

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 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 une fois qu'il sera connu quelle est la première étoile allant dans le deuxième bac, et la première étoile allant dans le troisième bac, etc. Cela est indiqué en plaçant $k - 1$ barres entre les étoiles. Parce qu'aucun bac n'est autorisé à être vide (toutes les variables sont positives), il n'y a au plus qu'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 ${\tbinom {n-1}{k-1}}$ combinaisons possibles.

Preuve du deuxième théorème[modifier | modifier le code]

Dans ce cas, accepter qu'un bac soit vide signifie que nous pouvons placer plusieurs barres entre les é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 ${\tbinom {n+k-1}{k-1}}$ arrangements possibles, on remarque que tout arrangement d'étoiles et de barres se compose d'un total de $n + k - 1$ objets, dont 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 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 positives équivaut à attribuer à chaque variable un 1 au préalable, et à demander le nombre de solutions lorsque chaque variable est non négative. Par exemple :

x_{1}+x_{2}+x_{3}+x_{4}=10

avec

x_{1},x_{2},x_{3},x_{4}>0

est équivalent à :

x_{1}+x_{2}+x_{3}+x_{4}=6

avec

x_{1},x_{2},x_{3},x_{4}\geq 0

Démonstrations à l'aide de fonctions génératrices[modifier | modifier le code]

Les deux cas sont très similaires ; dans le cas où $x_{i}\geq 0$ , chaque bac est représenté par la série génératrice $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 ${\frac {1}{1-x}}$ , et donc la fonction génératrice finale est ${\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 $x^{n}$ (écrit $[x^{n}]:$ ) de cette fonction

[x^{n}]:{\frac {1}{(1-x)^{k}}}

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

Dans le cas où $x_{i}>0$ , nous devons ajouter $x$ au numérateur pour indiquer qu'au moins une boule est dans le bac, obtenant : ${\frac {x}{1-x}}{\frac {x}{1-x}}\dots {\frac {x}{1-x}}={\frac {x^{k}}{(1-x)^{k}}}$ , et le coefficient de $x^{n}$ est alors ${\binom {n-1}{k-1}}$ .

Exemples[modifier | modifier le code]

Exemple 1[modifier | modifier le code]

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 ${\tbinom {7-1}{3-1}}=15$ façons de distribuer les pièces.

Exemple 2[modifier | modifier le code]

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 ${\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 ${\tbinom {16}{9}}=11440$ répartitions possibles de ces sept boules si on accepte les vides.

Exemple 3[modifier | modifier le code]

Nous pouvons utiliser cette méthode pour calculer le produit de Cauchy de $m$ copies de la série entière $\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 ${\tbinom {n-1}{m-1}}$ façons de former cette $n$ -ème puissance et $\left[\sum _{k=1}^{\infty }x^{k}\right]^{m}=\sum _{n=m}^{\infty }{{n-1} \choose {m-1}}x^{n}$

Exemple 4[modifier | modifier le code]

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 : $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[modifier | modifier le code]

↑ (en) J Batterson, Competition Math for Middle School, Art of Problem Solving
↑ (en) Philippe Flajolet et Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 26 juin 2009 (ISBN 978-0-521-89806-5)
↑ (en) « Art of Problem Solving », sur artofproblemsolving.com (consulté le 26 octobre 2021)
↑ (en) William Feller, An Introduction to Probability Theory and Its Applications, vol. 1, Wiley, 1968, 3rd éd., p. 38
↑ (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)
↑ (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)
↑ (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[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

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

Liens externes[modifier | modifier le code]

(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)

Portail des mathématiques

[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)

[:0-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)

[1]

[2]

[3]

[4]

[5]

[6]

[7]