Utilisateur:Dfeldmann/brouillon8

⇐ brouillon précédent Ceci est un brouillon de travail ; prière de ne pas le modifier ⇒ brouillon suivant

------- Section multiensemble ---------

Dénombrement des multiensembles

Bijection entre les 3-sous-ensembles d'un ensemble à 7 éléments (à gauche) et les 3-multiensembles avec des éléments provenant d'un ensemble à 5 éléments (à droite), ce qui illustre que ${\textstyle {7 \choose 3}=\left(\!\!{5 \choose 3}\!\!\right).}$

Le nombre de multiensembles de cardinal k, avec des éléments pris dans un ensemble fini de cardinal n, est parfois appelé le coefficient de multiensemble. Ce nombre est écrit par certains auteurs comme $\textstyle \left(\!\!{n \choose k}\!\!\right)$, une notation qui est censée ressembler à celle des coefficients binomiaux ; elle est utilisée par exemple dans (Stanley, 1997). Tout comme la loi binomiale implique des coefficients binomiaux, il existe une loi binomiale négative dans laquelle les coefficients de multiensemble apparaissent (ces coefficients ne doivent pas être confondus avec les coefficients multinomiaux qui apparaissent dans la loi multinomiale).

La valeur des coefficients de multiensemble peut être donnée explicitement par

$$\left(\!\!{n \choose k}\!\!\right)={n+k-1 \choose k}={\frac {(n+k-1)!}{k!\,(n-1)!}}={n(n+1)(n+2)\cdots (n+k-1) \over k!},$$

où la deuxième expression est un coefficient binomial ; de nombreux auteurs évitent en fait une notation distincte et écrivent simplement des coefficients binomiaux. Ainsi, le nombre de tels multiensembles est le même que le nombre de sous-ensembles de cardinal k d'un ensemble de cardinal n + k − 1. L'analogie avec les coefficients binomiaux peut être soulignée en écrivant le numérateur dans l'expression ci-dessus comme une puissance factorielle montante

$$\left(\!\!{n \choose k}\!\!\right)={n^{\overline {k}} \over k!},$$

pour correspondre à l'expression des coefficients binomiaux utilisant une puissance factorielle descendante :

$${n \choose k}={n^{\underline {k}} \over k!}.$$

La figure de droite montre une bijection entre les sous-ensembles à 3 éléments d'un ensemble à 7 éléments et les multiensembles à 3 éléments provenant d'un ensemble à 5 éléments, ce qui illustre que ${\textstyle {7 \choose 3}=\left(\!\!{5 \choose 3}\!\!\right).}$ Une façon simple de prouver cette égalité entre coefficients de multiensemble et coefficients binomiaux consiste à représenter les multiensembles par une série de points séparés par des barres : le multiensemble (6 a, 2 b, 3 c, 7 d) est noté $\cdot {\cdot }{\cdot }{\cdot }{\cdot }{\cdot }\vert {\cdot }{\cdot }\vert {\cdot }{\cdot }{\cdot }\vert {\cdot }{\cdot }{\cdot }{\cdot }{\cdot }{\cdot }{\cdot }$

Ce multiensemble de cardinal k = 18 est composé d'éléments d'un ensemble de cardinal n = 4. Le nombre de caractères incluant à la fois des points et des lignes verticales utilisés dans cette notation est 18 + 4 − 1. Le nombre de lignes verticales est 4 − 1. Le nombre de multiensembles de cardinal 18 est alors le nombre de façons d'arranger les 4 − 1 lignes verticales parmi les 18 + 4 − 1 caractères, et est donc le nombre de sous-ensembles de cardinal 4 − 1 d'un ensemble de cardinal 18 + 4 − 1. C'est donc bien que

$$\left(\!\!{18 \choose 4}\!\!\right)={4+18-1 \choose 4-1}={4+18-1 \choose 18}=1330,$$

donc la valeur du coefficient de et ses équivalences : Échec de l’analyse (fonction inconnue « \begin{align} »): {\displaystyle \begin{align} \left(!!{4\choose18}!!\right) &={21\choose18}=\frac{21!}{18!,3!}={21\choose3}, \[1ex] &=\frac{{\color{red}{\mathfrak{ 4\cdot5\cdot6\cdot7\cdot8\cdot9\cdot10\cdot11\cdot12\cdot13\cdot14\cdot15\cdot16\cdot17\cdot18}}} \cdot \mathbf{19\cdot20\cdot21}}{\mathbf{1\cdot2\cdot3} \cdot {\color{red}{\mathfrak{ 4\cdot5\cdot6\cdot7\cdot8\cdot9\cdot10\cdot11\cdot12\cdot13\cdot14\cdot15\cdot16\cdot17\cdot18}}}}, \[1ex] &=\frac{ 1\cdot2\cdot3\cdot4\cdot5\cdots16\cdot17\cdot18;\mathbf{\cdot;19\cdot20\cdot21}} {,1\cdot2\cdot3\cdot4\cdot5\cdots 16\cdot17\cdot18;\mathbf{\cdot;1\cdot2\cdot3\quad}}, \[1ex] &=\frac{19\cdot20\cdot21}{1\cdot2\cdot3}. \end{align}} De la relation entre les coefficients binomiaux et les coefficients de multiset, il s'ensuit que le nombre de multisets de cardinalité k dans un ensemble de cardinalité n peut être écrit

$$\left(!!{n \choose k}!!\right)=(-1)^{k}{-n \choose k}.$$

De plus,

$$\left(!!{n \choose k}!!\right)=\left(!!{k+1 \choose n-1}!!\right).$$

Relation de récurrence

Une relation de récurrence pour les coefficients de multiset peut être donnée comme suit :

$$\left(!!{n \choose k}!!\right)=\left(!!{n \choose k-1}!!\right)+\left(!!{n-1 \choose k}!!\right)\quad {\mbox{pour }}n,k>0$$

avec

$$\left(!!{n \choose 0}!!\right)=1,\quad n\in \mathbb {N} ,\quad {\mbox{et}}\quad \left(!!{0 \choose k}!!\right)=0,\quad k>0.$$

La récurrence ci-dessus peut être interprétée comme suit. Soit $[n]:={1,\dots ,n}$ l'ensemble source. Il y a toujours exactement un (vide) multiset de taille 0, et si n = 0 il n'y a pas de multisets plus grands, ce qui donne les conditions initiales. Maintenant, considérez le cas où n, k > 0. Un multiset de cardinalité k avec des éléments de [n] pourrait ou non contenir un quelconque élément n. S'il apparaît, alors en enlevant n une fois, il reste un multiset de cardinalité k − 1 d'éléments de [n], et chaque tel multiset peut apparaître, ce qui donne un total de

$$\left(!!{n \choose k-1}!!\right)$$

possibilités. Si n n'apparaît pas, alors notre multiset original est égal à un multiset de cardinalité k avec des éléments de [n − 1], dont il existe

$$\left(!!{n-1 \choose k}!!\right).$$

Ainsi,

$$\left(!!{n \choose k}!!\right)=\left(!!{n \choose k-1}!!\right)+\left(!!{n-1 \choose k}!!\right).$$

=== Séries génératrices === La fonction génératrice des coefficients de multiset est très simple :

$$\sum _{d=0}^{\infty }\left(!!{n \choose d}!!\right)t^{d}={\frac {1}{(1-t)^{n}}}.$$

Comme les multisets sont en correspondance un-à-un avec les monômes, $\left(!!{n \choose d}!!\right)$ est aussi le nombre de monômes de degré d en n indéterminées. Ainsi, la série ci-dessus est également la série de Hilbert de l'anneau de polynômes $k[x_{1},\ldots ,x_{n}].$ Comme $\left(!!{n \choose d}!!\right)$ est un polynôme en n, il et la fonction génératrice sont bien définis pour toute valeur complexe de n. === Généralisation et lien avec la série binomiale négative === La formule multiplicative permet d'étendre la définition des coefficients de multiset en remplaçant n par un nombre arbitraire α (négatif, réel, ou complexe) :

$$\left(!!{\alpha \choose k}!!\right)={\frac {\alpha ^{\overline {k}}}{k!}}={\frac {\alpha (\alpha +1)(\alpha +2)\cdots (\alpha +k-1)}{k(k-1)(k-2)\cdots 1}}\quad {\text{pour }}k\in \mathbb {N} {\text{ et arbitraire }}\alpha .$$

Avec cette définition, on obtient une généralisation de la formule binomiale négative (avec l'une des variables fixée à 1), ce qui justifie de nommer les $\left(!!{\alpha \choose k}!!\right)$ coefficients binomiaux négatifs :

$$(1-X)^{-\alpha }=\sum _{k=0}^{\infty }\left(!!{\alpha \choose k}!!\right)X^{k}.$$

Cette formule de série de Taylor est valable pour tous les nombres complexes α et X avec < 1. Elle peut aussi être interprétée comme une identité de série formelle en X, où elle peut effectivement servir de définition des puissances arbitraires de séries avec un coefficient constant égal à 1 ; l'idée est qu'avec cette définition, toutes les identités attendues pour l'exponentiation sont valides, notamment

$$(1-X)^{-\alpha }(1-X)^{-\beta }=(1-X)^{-(\alpha +\beta )}\quad {\text{et}}\quad ((1-X)^{-\alpha })^{-\beta }=(1-X)^{-(-\alpha \beta )},$$

et des formules telles que celles-ci peuvent être utilisées pour prouver des identités pour les coefficients de multiset. Si α est un entier non positif n, alors tous les termes avec k > −n sont nuls, et la série infinie devient une somme finie. Cependant, pour d'autres valeurs de α, y compris les entiers positifs et les rationnels, la série est infinie.

---

Article étoiles et barres ------------

En combinatoire, la méthode des étoiles et barres (également appelée "bâtons et pierres", "boules et barres", et "points et séparateurs") 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.

É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 la combinatoire élémentaire concernant le nombre de solutions à une équation.

Premier théorème

Pour toute paire d'entier positif n et k, le nombre de k-tuples d'entiers positifs dont la somme est 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₁ + x₂ + x₃ + x₄ = 10 (avec x₁, x₂, x₃, x₄ > 0) comme le coefficient binomial :${\binom {n-1}{k-1}}={\binom {10-1}{4-1}}={\binom {9}{3}}=84.$ Cela correspond aux compositions d'un entier.

Deuxième théorème

Pour toute paire d'entiers positifs n et k, le nombre de k-tuples d'entiers non négatifs dont la somme est n est égal au nombre de multisets de cardinalité n pris dans un ensemble de taille k, ou équivalemment, le nombre de multisets de cardinalité 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₄ $\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$ :${\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

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-tuple d'entiers positifs, comme dans l'énoncé du théorème. Par exemple, avec n = 7 et k = 3, commençons par placer les étoiles en ligne : Modèle:Image frame 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 : Modèle:Image frame 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

Dans ce cas, la restriction assouplie de la non-négativité au lieu de la positivité 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 tuple (4, 0, 1, 2, 0) peut être représenté par le diagramme suivant : Modèle:Image frame Pour voir qu'il y a ${\tbinom {n+k-1}{k-1}}$ arrangements possibles, observons 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é en 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$

Preuves par fonctions génératrices

Les deux cas sont très similaires, nous allons d'abord examiner le cas où $x_{i}\geq 0$. Le 'seau' devient

${\frac {1}{1-x}}$

Cela peut aussi être écrit comme

$1+x+x^{2}+\dots$

et l'exposant de x nous indique combien de boules sont placées dans le seau. Chaque seau 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}}}$

Comme nous n'avons que n boules, nous voulons le coefficient de $x^{n}$ (écrit $[x^{n}]:$) de cette fonction

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

C'est une fonction génératrice bien connue - elle génère les diagonales dans Pascal's Triangle, et le coefficient de $x^{n}$ est

${\binom {n+k-1}{k-1}}$

Dans le cas où $x_{i}>0$, nous devons ajouter x au numérateur pour indiquer qu'au moins une boule est dans le seau.

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

${\binom {n-1}{k-1}}$

Exemples

De nombreux problèmes de mots élémentaires en combinatoire sont résolus par les théorèmes ci-dessus.

Quatre cookies sont distribués entre Tom, Dick, and 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 caret 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 ${\tbinom {3}{2}}.$ Sont également montrées les trois 3-compositions de 4.

La combinaison trois-choisir-deux donne deux résultats, selon qu'un bac est autorisé à avoir zéro élément. Dans les deux cas, le nombre de bacs est 3. Si zéro n'est pas autorisé, le nombre de cookies est n = 6, comme décrit dans la figure précédente. Si zéro est autorisé, le nombre de cookies n'est que de n = 3.

Exemple 1

Si l'on souhaite compter le nombre de façons de distribuer sept pièces de un dollar indistinguables entre Amber, Ben et Curtis de sorte que chacun reçoive au moins un dollar, on peut observer que les distributions sont essentiellement équivalentes aux tuples de trois entiers positifs dont la somme est 7. (Ici, la première entrée du tuple est le nombre de pièces données à Amber, et ainsi de suite.) Ainsi, le premier théorème des étoiles et des barres s'applique, 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

Si n = 5, k = 4, et un ensemble de taille k est {a, b, c, d}, alors ★|★★★||★ pourrait représenter soit le multiset {a, b, b, b, d} soit le 4-tuple (1, 3, 0, 1). La représentation de tout multiset pour cet exemple devrait utiliser SAB2 avec n = 5, k – 1 = 3 barres pour donner ${\tbinom {5+4-1}{4-1}}={\tbinom {8}{3}}=56$.

Exemple 3

SAB2 permet d'avoir plus de barres que d'étoiles, ce qui n'est pas permis dans SAB1. Ainsi, par exemple, 10 boules dans 7 bacs est ${\tbinom {16}{6}}$, tandis que 7 boules dans 10 bacs est ${\tbinom {16}{9}}$, avec 6 boules dans 11 bacs comme ${\tbinom {16}{10}}={\tbinom {16}{6}}.$

Exemple 4

Si nous avons la série entière infinie :$\left[\sum _{k=1}^{\infty }x^{k}\right],$ nous pouvons utiliser cette méthode pour calculer le produit de Cauchy de m copies de la série. Pour le n-ème terme de l'expansion, 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 notre n-ème puissance : :$\left[\sum _{k=1}^{\infty }x^{k}\right]^{m}=\sum _{n=m}^{\infty }{{n-1} \choose {m-1}}x^{n}$

Exemple 5

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 P éléments d'énergie ε sur N résonateurs. 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). Ils ont choisi le 4-uplet (4, 2, 0, 1) comme exemple illustratif pour cette représentation symbolique : εεεε0εε00ε. ==Voir aussi== *Coefficient binomial gaussien *Partition (théorie des nombres) *Twelvefold way *Distribution multinomiale de Dirichlet

==Références==

==Lecture complémentaire== *(en) Jim Pitman, Probability, Berlin, Springer-Verlag, 1993 (ISBN 0-387-97974-3) *Eric W. Weisstein, « Multichoose », Mathworld -- A Wolfram Web Resource (consulté le 18 novembre 2012)

ChatGPT peut faire des erreurs. Envisagez de vérifier les informations importantes.

In the context of combinatorial mathematics, stars and bars (also called "sticks and stones", "balls and bars", and "dots and dividers") is a graphical aid for deriving certain combinatorial theorems. It can be used to solve many simple counting problems, such as how many ways there are to put n indistinguishable balls into k distinguishable bins.

Statements of theorems

The stars and bars method is often introduced specifically to prove the following two theorems of elementary combinatorics concerning the number of solutions to an equation.

Theorem one

For any pair of positive integers n and k, the number of k-tuples of positive integers whose sum is n is equal to the number of (k − 1)-element subsets of a set with n − 1 elements.

For example, if n = 10 and k = 4, the theorem gives the number of solutions to x₁ + x₂ + x₃ + x₄ = 10 (with x₁, x₂, x₃, x₄ > 0) as the binomial coefficient

${\binom {n-1}{k-1}}={\binom {10-1}{4-1}}={\binom {9}{3}}=84.$

This corresponds to compositions of an integer.

Theorem two

For any pair of positive integers n and k, the number of k-tuples of non-negative integers whose sum is n is equal to the number of multisets of cardinality n taken from a set of size k, or equivalently, the number of multisets of cardinality k − 1 taken from a set of size n + 1.

For example, if n = 10 and k = 4, the theorem gives the number of solutions to x₁ + x₂ + x₃ + x₄ = 10 (with x₁, x₂, x₃, x₄ $\geq 0$ ) as:

$\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$

${\binom {n+k-1}{k-1}}={\binom {10+4-1}{4-1}}={\binom {13}{3}}=286$

This corresponds to weak compositions of an integer.

Proofs via the method of stars and bars

Theorem one proof

Suppose there are n objects (represented here by stars) to be placed into k bins, such that all bins contain at least one object. The bins are distinguishable (say they are numbered 1 to k) but the n stars are not (so configurations are only distinguished by the number of stars present in each bin). A configuration is thus represented by a k-tuple of positive integers, as in the statement of the theorem.

For example, with n = 7 and k = 3, start by placing the stars in a line:

The configuration will be determined once it is known which is the first star going to the second bin, and the first star going to the third bin, etc.. This is indicated by placing k − 1 bars between the stars. Because no bin is allowed to be empty (all the variables are positive), there is at most one bar between any pair of stars.

For example:

There are n − 1 gaps between stars. A configuration is obtained by choosing k − 1 of these gaps to contain a bar; therefore there are ${\tbinom {n-1}{k-1}}$ possible combinations.

Theorem two proof

In this case, the weakened restriction of non-negativity instead of positivity means that we can place multiple bars between stars, before the first star and after the last star.

For example, when n = 7 and k = 5, the tuple (4, 0, 1, 2, 0) may be represented by the following diagram:

To see that there are ${\tbinom {n+k-1}{k-1}}$ possible arrangements, observe that any arrangement of stars and bars consists of a total of n + k − 1 objects, n of which are stars and k − 1 of which are bars. Thus, we only need to choose k − 1 of the n + k − 1 positions to be bars (or, equivalently, choose n of the positions to be stars).

Theorem 1 can now be restated in terms of Theorem 2, because the requirement that all the variables are positive is equivalent to pre-assigning each variable a 1, and asking for the number of solutions when each variable is non-negative.

For example:

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

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

is equivalent to:

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

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

Proofs by generating functions

Both cases are very similar, we will look at the case when $x_{i}\geq 0$ first. The 'bucket' becomes

${\frac {1}{1-x}}$

This can also be written as

$1+x+x^{2}+\dots$

and the exponent of x tells us how many balls are placed in the bucket.

Each additional bucket is represented by another ${\frac {1}{1-x}}$, and so the final generating function is

${\frac {1}{1-x}}{\frac {1}{1-x}}\dots {\frac {1}{1-x}}={\frac {1}{(1-x)^{k}}}$

As we only have n balls, we want the coefficient of $x^{n}$ (written $[x^{n}]:$) from this

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

This is a well-known generating function - it generates the diagonals in Pascal's Triangle, and the coefficient of $x^{n}$ is

${\binom {n+k-1}{k-1}}$

For the case when $x_{i}>0$, we need to add x into the numerator to indicate that at least one ball is in the bucket.

${\frac {x}{1-x}}{\frac {x}{1-x}}\dots {\frac {x}{1-x}}={\frac {x^{k}}{(1-x)^{k}}}$

and the coefficient of $x^{n}$ is

${\binom {n-1}{k-1}}$

Examples

Many elementary word problems in combinatorics are resolved by the theorems above.

Four cookies are distributed between Tom, Dick, and Harry (TDH) in such a way that each gets at least one cookie. The 4 cookies are traditionally represented as stars (****). But here, they are shown as cookie-colored circles (●●●●). The 3 gaps between the cookies are indicated by red carets (^ ^ ^). With three people, we need 2 bar symbols (| |) to occupy any two of the three gaps. Hence the problem reduces to finding the binomial coefficient ${\tbinom {3}{2}}.$ Also shown are the three corresponding 3-compositions of 4.

The three-choose-two combination yields two results, depending on whether a bin is allowed to have zero items. In both cases the number of bins is 3. If zero is not allowed, the number of cookies is n = 6, as described in the previous figure. If zero is allowed, the number of cookies is only n = 3.

Example 1

If one wishes to count the number of ways to distribute seven indistinguishable one dollar coins among Amber, Ben, and Curtis so that each of them receives at least one dollar, one may observe that distributions are essentially equivalent to tuples of three positive integers whose sum is 7. (Here the first entry in the tuple is the number of coins given to Amber, and so on.) Thus stars and bars theorem 1 applies, with n = 7 and k = 3, and there are ${\tbinom {7-1}{3-1}}=15$ ways to distribute the coins.

Example 2

If n = 5, k = 4, and a set of size k is {a, b, c, d}, then ★|★★★||★ could represent either the multiset {a, b, b, b, d} or the 4-tuple (1, 3, 0, 1). The representation of any multiset for this example should use SAB2 with n = 5, k – 1 = 3 bars to give ${\tbinom {5+4-1}{4-1}}={\tbinom {8}{3}}=56$.

Example 3

SAB2 allows for more bars than stars, which isn't permitted in SAB1.

So, for example, 10 balls into 7 bins is ${\tbinom {16}{6}}$, while 7 balls into 10 bins is ${\tbinom {16}{9}}$, with 6 balls into 11 bins as ${\tbinom {16}{10}}={\tbinom {16}{6}}.$

Example 4

If we have the infinite power series

$\left[\sum _{k=1}^{\infty }x^{k}\right],$

we can use this method to compute the Cauchy product of m copies of the series. For the nth term of the expansion, we are picking n powers of x from m separate locations. Hence there are ${\tbinom {n-1}{m-1}}$ ways to form our nth power:

$\left[\sum _{k=1}^{\infty }x^{k}\right]^{m}=\sum _{n=m}^{\infty }{{n-1} \choose {m-1}}x^{n}$

Example 5

The graphical method was used by Paul Ehrenfest and Heike Kamerlingh Onnes—with symbol ε (quantum energy element) in place of a star and the symbol 0 in place of a bar—as a simple derivation of Max Planck's expression for the number of "complexions" for a system of "resonators" of a single frequency.

By complexions (microstates) Planck meant distributions of P energy elements ε over N resonators. The number R of complexions is

$R={\frac {(N+P-1)!}{P!(N-1)!}}.\$

The graphical representation of each possible distribution would contain P copies of the symbol ε and N – 1 copies of the symbol 0. In their demonstration, Ehrenfest and Kamerlingh Onnes took N = 4 and P = 7 (i.e., R = 120 combinations). They chose the 4-tuple (4, 2, 0, 1) as the illustrative example for this symbolic representation: εεεε0εε00ε.

See also

• Gaussian binomial coefficient
• Partition (number theory)
• Twelvefold way
• Dirichlet-multinomial distribution

Further reading

• (en) Jim Pitman, Probability, Berlin, Springer-Verlag, 1993 (ISBN 0-387-97974-3)
• Eric W. Weisstein, « Multichoose », Mathworld -- A Wolfram Web Resource (consulté le 18 novembre 2012)