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 x1 + x2 + x3 + x4 = 10 (avec x1, x2, x3, x4 > 0) est égal au coefficient binomial :
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 . 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 x1 + x2 + x3 + x4 = 10 (avec x1, x2, x3, x4 ) comme étant égal à :, ou , (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 ★ :
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 :
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 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 :
Pour voir qu'il y a configurations possibles, on remarque que toute configuration d'étoiles et de barres se compose d'un total de n + k − 1 objets, dont é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 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 :
- avec
est équivalent à :
- avec
Démonstrations à l'aide de fonctions génératrices
Les deux cas sont très similaires ; dans le cas où , chaque bac est représenté par la série génératrice , 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 , et donc la fonction génératrice finale est
Pour déterminer le nombre de façon de placer n boules, on cherche le coefficient de (écrit ) de cette fonction
La série de Taylor de cette fonction (obtenue en dérivant k fois la série ) est .
Dans le cas où , nous devons ajouter x au numérateur pour indiquer qu'au moins une boule est dans le bac, obtenant : , et le coefficient de est alors .
Exemples
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/ba/Colored_circle_starsbars_1.svg/220px-Colored_circle_starsbars_1.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/78/Stars_bars_5_take_2.svg/220px-Stars_bars_5_take_2.svg.png)
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 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 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 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 : 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 façons de former cette n-ème puissance et
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 : 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
- ↑ (en) J Batterson, Competition Math for Middle School, Art of Problem Solving
- ↑ (en) Philippe Flajolet et Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, (ISBN 978-0-521-89806-5)
- ↑ (en) « Art of Problem Solving », sur artofproblemsolving.com (consulté le )
- ↑ (en) William Feller, An Introduction to Probability Theory and Its Applications, vol. 1, Wiley, , 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, no 170, , p. 297–301 (DOI 10.1080/14786440208635308, lire en ligne, consulté le )
- ↑ (de) Max Planck, « Ueber das Gesetz der Energieverteilung im Normalspectrum », Annalen der Physik, vol. 309, no 3, , 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, , p. 170–215 (DOI 10.1007/s00016-002-8363-7, lire en ligne, consulté le )
Voir aussi
Articles connexes
Bibliographie
(en) Jim Pitman, Probability, Berlin, Springer-Verlag, (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 )
Portail des mathématiques