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, des ronds et des barres, ou des points et des séparateurs) 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 Modèle:Mvar boules indiscernables dans Modèle:Mvar bacs discernables.

É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 Modèle:Mvar et Modèle:Mvar, le nombre de Modèle:Mvar-uplets d'entiers strictement positifs dont la somme vaut Modèle:Mvar, c'est-à-dire le nombre de compositions de Modèle:Mvar, est égal au nombre de parties à Modèle:Math éléments d'un ensemble à Modèle:Math éléments. Par exemple, si Modèle:Math et Modèle:Math, le théorème montre que le nombre de solutions de Modèle:Math (avec Modèle:Math) est égal au coefficient binomial :$(\genfrac{}{}{0ex}{}{n-1}{k-1})=(\genfrac{}{}{0ex}{}{10-1}{4-1})=(\genfrac{}{}{0ex}{}{9}{3})=84.$

Deuxième théorème

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

Par exemple, si Modèle:Math et Modèle:Math, le théorème donne le nombre de solutions de Modèle:Math (avec Modèle:Math) comme étant égal à :$\left((\genfrac{}{}{0ex}{}{k}{n})\right)=(\genfrac{}{}{0ex}{}{k+n-1}{n})=(\genfrac{}{}{0ex}{}{13}{10})=286$, ou $\left((\genfrac{}{}{0ex}{}{n+1}{k-1})\right)=(\genfrac{}{}{0ex}{}{n+1+k-1-1}{k-1})=(\genfrac{}{}{0ex}{}{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 Modèle:Mvar objets (représentés ici par des étoiles) à placer dans Modèle:Mvar 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 à Modèle:Mvar) mais les Modèle:Mvar é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 Modèle:Mvar-uplet d'entiers strictement positifs, comme dans l'énoncé du théorème. Par exemple, avec Modèle:Math et Modèle:Math, on commence par placer les étoiles en ligne ★ : Modèle:Vignette multiple 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 Modèle:Math 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  : Modèle:Vignette multiple Il y a Modèle:Math espaces entre les étoiles. Une configuration est obtenue en choisissant Modèle:Math de ces espaces pour contenir une barre ; il y a donc $(\genfrac{}{}{0ex}{}{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 Modèle:Math et Modèle:Math, le 5-uplet (4, 0, 1, 2, 0) peut être représenté par le diagramme suivant : Modèle:Vignette multiple Pour voir qu'il y a $(\genfrac{}{}{0ex}{}{n+k-1}{k-1})$ configurations possibles, on remarque que toute configuration d'étoiles et de barres se compose d'un total de Modèle:Math objets, dont $n$ étoiles et Modèle:Math barres. Ainsi, nous avons seulement besoin de choisir Modèle:Math des Modèle:Math 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 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 :

$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⩾0$

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

Les deux cas sont très similaires. Dans le cas où $x_i⩾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 Modèle:Mvar nous indique combien de boules sont placées dans le bac. Chaque bac supplémentaire est représenté par un facteur $\frac{1}{1-x}$, et donc la fonction génératrice finale est $\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

$(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 $x^{m_i}$ dans le Modèle:Mvar-ème facteur, pour chaque Modèle:Mvar entre 1 et Modèle:Mvar et le monôme correspondant est de degré $m_1+\cdots +m_k$. Autrement dit chaque composition de Modèle:Mvar contribue pour 1 au terme de degré Modèle:Mvar de la série génératrice.)

Pour déterminer le nombre de façon de placer Modèle:Mvar boules, on cherche donc le coefficient de $x^n$ de cette série, qui est noté

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

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

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

Exemples

Erreur lors de la création de la vignette :

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 (Modèle:Color). Les 3 espaces entre les cookies sont indiqués par des carets rouges (Modèle:Red). 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 $(\genfrac{}{}{0ex}{}{3}{2}).$ Sont également montrées les trois 3-compositions de 4.

Erreur lors de la création de la vignette :

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 Modèle:Math. Si zéro est autorisé, le nombre de cookies n'est que de Modèle:Math, 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 Modèle:Math et Modèle:Math, et il y a $(\genfrac{}{}{0ex}{}{7-1}{3-1})=15$ façons de distribuer les pièces.

Exemple 2

Si Modèle:Math, Modèle:Math, l'ensemble de taille Modèle:Mvar étant Modèle:Math alors ★|★★★||★ pourrait représenter le multiensemble Modèle:Math ou le 4-uplet Modèle:Math Cette représentation avec Modèle:Math étoiles et Modèle:Math barres montre donc qu'il y a $(\genfrac{}{}{0ex}{}{5+4-1}{4-1})=(\genfrac{}{}{0ex}{}{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 $(\genfrac{}{}{0ex}{}{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 Modèle:Mvar copies de la série entière $\sum _{k=1}^{\mathrm{\infty }}{x}^k=\frac{x}{1-x}$ : pour le Modèle:Mvar-ième terme de ce développement, nous choisissons Modèle:Mvar puissances de Modèle:Mvar parmi Modèle:Mvar emplacements séparés. Il y a donc $(\genfrac{}{}{0ex}{}{n-1}{m-1})$ façons de former cette Modèle:Mvar-ième puissance et ${\left[\sum _{k=1}^{\mathrm{\infty }}{x}^k\right]}^m=\sum _{n=m}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{n-1}{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. Par complexions (micro-états), Planck entendait la distribution des Modèle:Mvar éléments d'énergie ε sur Modèle:Mvar résonateursModèle:,. Le nombre Modèle:Mvar de complexions est $R=\frac{(N+P-1)!}{P!(N-1)!}.$ La représentation graphique de chaque distribution possible contiendrait Modèle:Mvar copies du symbole ε et Modèle:Math copies du symbole 0. Dans leur démonstration, Ehrenfest et Kamerlingh Onnes ont pris Modèle:Math et Modèle:Math (c'est-à-dire Modèle:Math combinaisons), et ils ont choisi le 4-uplet (4, 2, 0, 1) comme exemple illustratif pour cette représentation symbolique : εεεε0εε00ε.

Voir aussi

Articles connexes

• Partition d'un entier
• Coefficient binomial de Gauss

Liens externes

• Modèle:Lien web