Stars and bars (combinatorics): Difference between revisions

Revision as of 14:39, 16 August 2024

Latest revision as of 16:05, 19 August 2025

(36 intermediate revisions by 16 users not shown)

Line 1:

{{short description|Graphical aid for deriving some concepts in combinatorics}}

In the context of [[combinatorial mathematicscombinatorics]], '''stars and bars''' (also called "sticks and stones",<ref>{{Cite book|last=Batterson|first=J|title=Competition Math for Middle School|publisher=Art of Problem Solving}}</ref> "balls and bars",<ref>{{cite book|last1=Flajolet|first1=Philippe|last2=Sedgewick|first2=Robert|date=June 26, 2009|title=Analytic Combinatorics|publisher=Cambridge University Press|isbn = 978-0-521-89806-5}}</ref> and "dots and dividers"<ref name=":0">{{Cite web|title=Art of Problem Solving|url=https://artofproblemsolving.com/wiki/index.php/Ball-and-urn|access-date=2021-10-26|website=artofproblemsolving.com}}</ref>) is a graphical aid for deriving certain [[combinatorial]] theorems. It can be used to solve manya simplevariety of [[combinatorial enumeration|counting problems]], such as how many ways there are to put {{mvar|n}} indistinguishable balls into {{mvar|k}} distinguishable bins.<ref>{{cite book |last=Feller |first=William |author-link=William Feller |year=1968 |title=An Introduction to Probability Theory and Its Applications |publisher=Wiley |volume=1 |edition=3rd |page=38}}</ref> The solution to this particular problem is given by the binomial coefficient <math>\tbinom{n+k-1}{k-1}</math>, which is the number of subsets of size {{math|''k'' − 1}} that can be formed from a set of size {{math|''n'' + ''k'' − 1}}.

If, for example, there are two balls and three bins, then the number of ways of placing the balls is <math>\tbinom{2+3-1}{3-1} = \tbinom{4}{2} = 6</math>. The table shows the six possible ways of distributing the two balls, the strings of stars and bars that represent them (with stars indicating balls and bars separating bins from one another), and the subsets that correspond to the strings. As two bars are needed to separate three bins and there are two balls, each string contains two bars and two stars. Each subset indicates which of the four symbols in the corresponding string is a bar.

Theorems one and two are the coefficients used for 2 different support ranges in the [[Negative binomial distribution|negative binomial probability distribution]].

{| class="wikitable"

|+ Six configurations of two balls in three bins and their star and bar representations

|-

! Bin 1 !! Bin 2 !! Bin 3 !! String !! Subset of {1,2,3,4}

|-

| 2 || 0 || 0 || ★ ★ {{pipe}} {{pipe}} || {3,4}

|-

| 1 || 1 || 0 || ★ {{pipe}} ★ {{pipe}} || {2,4}

|-

| 1 || 0 || 1 || ★ {{pipe}} {{pipe}} ★ || {2,3}

|-

| 0 || 2 || 0 || {{pipe}} ★ ★ {{pipe}} || {1,4}

|-

| 0 || 1 || 1 || {{pipe}} ★ {{pipe}} ★ || {1,3}

|-

| 0 || 0 || 2 || {{pipe}} {{pipe}} ★ ★ || {1,2}

|}

==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 integer]]s {{mvar|n}} and {{mvar|k}}, the number of {{mvar|k}}-[[tuple]]s of '''positive''' integers whose sum is {{mvar|n}} is equal to the number of {{math|(''k'' − 1)}}-element subsets of a set with {{math|''n'' − 1}} elements.

For example, if {{math|1=''n'' = 10}} and {{math|1=''k'' = 4}}, the theorem gives the number of solutions to {{math|1=''x''{{sub|1}} + ''x''{{sub|2}} + ''x''{{sub|3}} + ''x''{{sub|4}} = 10}} (with {{math|''x''{{sub|1}}, ''x''{{sub|2}}, ''x''{{sub|3}}, ''x''{{sub|4}} > 0}}) as the [[binomial coefficient]]

:<math>\binom{n - 1}{k - 1} = \binom{10 - 1}{4 - 1} = \binom{9}{3} = 84.,</math>

where <math>\tbinom{n - 1}{k - 1}</math> is the number of [[combination]]s of {{math|''n'' − 1}} elements taken {{math|''k'' − 1}} at a time.

This corresponds to [[Composition (combinatorics)|compositions]] of an integer.

===Theorem two===

For any pair of positive integers {{mvar|n}} and {{mvar|k}}, the number of {{mvar|k}}-[[tuple]]s of '''non-negative''' integers whose sum is {{mvar|n}} is equal to the number of [[multiset]]s of size {{math|''k'' − 1}} taken from a set of size {{math|''n'' + 1}}, or equivalently, the number of multisets of size {{math|''n''}} taken from a set of size {{math|''k''}}, and is given by

:<math>\binom{n + k - 1}{k - 1}.</math>

For example, if {{math|1=''n'' = 10}} and {{math|1=''k'' = 4}}, the theorem gives the number of solutions to {{math|1=''x''{{sub|1}} + ''x''{{sub|2}} + ''x''{{sub|3}} + ''x''{{sub|4}} = 10}} (with {{math|''x''{{sub|1}}, ''x''{{sub|2}}, ''x''{{sub|3}}, ''x''{{sub|4}} <math>\ge0</math> }}) as

For any pair of positive integers {{mvar|n}} and {{mvar|k}}, the number of {{mvar|k}}-[[tuple]]s of '''non-negative''' integers whose sum is {{mvar|n}} is equal to the number of [[multiset]]s of [[cardinality]] {{math|''n''}} taken from a set of size {{math|''k''}}, or equivalently, the number of multisets of cardinality {{math|''k'' − 1}} taken from a set of size {{math|''n'' + 1}}.

:<math>\left(\!\!{n+1\choose k-1}\!\!\right) = \left(\!\!{k\choose n}\!\!\right) = \binom{n + k - 1}{k - 1} = \binom{10+4-1}{4 - 1} = \binom{13}{3} = 286,</math>

where the [[Multiset#Counting multisets|multiset coefficient]] <math>\left(\!\!\binom{k}{n}\!\!\right)</math> is the number of multisets of size {{mvar|n}}, with elements taken from a set of size {{mvar|k}}.

This corresponds to [[Composition (combinatorics)|weak compositions]] of an integer. With {{mvar|k}} fixed, the numbers for {{math|''n'' {{=}} 0, 1, 2, 3, ...}} are those in the {{math|(''k'' − 1)}}st diagonal of [[Pascal's triangle]]. For example, when {{math|''k'' {{=}} 3}} the {{mvar|n}}th number is the {{math|(''n'' + 1)}}st [[triangular number]], which falls on the second diagonal, 1, 3, 6, 10, ....

For example, if {{math|1=''n'' = 10}} and {{math|1=''k'' = 4}}, the theorem gives the number of solutions to {{math|1=''x''{{sub|1}} + ''x''{{sub|2}} + ''x''{{sub|3}} + ''x''{{sub|4}} = 10}} (with {{math|''x''{{sub|1}}, ''x''{{sub|2}}, ''x''{{sub|3}}, ''x''{{sub|4}} <math>\ge0</math> }}) as:

:<math>\left(\!\!{k\choose n}\!\!\right) = {k+n-1 \choose n} = \binom{13}{10} = 286</math>

:<math>\left(\!\!{n+1\choose k-1}\!\!\right) = {n+1+k-1-1 \choose k-1} = \binom{13}{3} = 286</math>

:<math>\binom{n + k - 1}{k - 1} = \binom{10+4-1}{4 - 1} = \binom{13}{3} = 286</math>

This corresponds to [[Composition (combinatorics)|weak compositions]] of an integer.

==Proofs via the method of stars and bars==

===Theorem one proof===

SupposeThe thereproblem areof enumerating ''k''-tuples whose sum is ''n'' objectsis (representedequivalent hereto bythe stars)problem of counting configurations of the following kind: let there be ''n'' objects to be placed into ''k'' bins, suchso that all bins contain at least one object. The bins are distinguishabledistinguished (say they are numbered 1 to ''k'') but the ''n'' starsobjects are not (so configurations are only distinguished by the ''number of starsobjects'' present in each bin). A configuration is thus represented by a ''k''-tuple of positive integers, as in the statement of the theorem.

The ''n'' objects are now represented as a row of ''n'' stars; adjacent bins are separated by bars. The configuration will be specified by indicating the boundary between the first and second bin, the boundary between the second and third bin, and so on. Hence {{math|''k'' − 1}} bars need to be placed between stars. Because no bin is allowed to be empty, there is at most one bar between any pair of stars. There are {{math|''n'' − 1}} gaps between stars and hence {{math|''n'' − 1}} positions in which a bar may be placed. A configuration is obtained by choosing {{math|''k'' − 1}} of these gaps to contain a bar; therefore there are <math>\tbinom{n - 1}{k - 1}</math> configurations.

===Example===

For example, with {{math|''n'' {{=}} 7}} and {{math|''k'' {{=}} 3}}, start by placing the stars in a line:

With {{math|''n'' {{=}} 7}} and {{math|''k'' {{=}} 3}}, start by placing seven stars in a line:

{{image frame

Line 43 ⟶ 61:

}}

Now indicate the boundaries between the bins:

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 {{math|''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:

{{image frame

|align=center

|content=

{{nowrap|{{huge|★ ★ ★ ★ &#124;{{pipe}} ★ &#124;{{pipe}} ★ ★}}}}

|caption=Fig.&nbsp;2: These two bars give rise to three bins containing 4, 1, and 2 objects

}}

ThereIn aregeneral {{math|''n''two −of 1}}the gapssix betweenpossible stars.bar Apositions configurationmust isbe obtainedchosen. by choosing {{math|''k'' − 1}} of these gaps to contain a bar; thereforeTherefore there are <math>\tbinom{n - 16}{k2} -= 1}15</math> possiblesuch [[combinations]]configurations.

===Theorem two proof===

In this case, the weakened restriction of non-negativity instead of positivity means that we can place multiple bars between stars and that one or more bars also be placed before the first star and after the last star. In terms of configurations involving objects and bins, bins are now allowed to be empty.

Rather than a {{math|(''k'' − 1)}}-set of bar positions taken from a set of size {{math|''n'' − 1}} as in the proof of Theorem one, we now have a {{math|(''k'' − 1)}}-multiset of bar positions taken from a set of size {{math|''n'' + 1}} (since bar positions may repeat and since the ends are now allowed bar positions). An alternative interpretation in terms of multisets is the following: there is a set of {{mvar|k}} bin labels from which a multiset of size {{mvar|n}} is to be chosen, the multiplicity of a bin label in this multiset indicating the number of objects placed in that bin. The equality <math>\left(\!\!{n+1\choose k-1}\!\!\right) = \left(\!\!{k\choose n}\!\!\right)</math> can also be understood as an equivalence of different counting problems: the number of {{mvar|k}}-tuples of non-negative integers whose sum is {{mvar|n}} equals the number of {{math|(''n'' + 1)}}-tuples of non-negative integers whose sum is {{math|''k'' − 1}}, which follows by interchanging the roles of bars and stars in the diagrams representing configurations.

To see the expression <math>\tbinom{n + k - 1}{k-1}</math> directly, observe that any arrangement of stars and bars consists of a total of {{math|''n'' + ''k'' − 1}} symbols, {{mvar|n}} of which are stars and {{math|''k'' − 1}} of which are bars. Thus, we may lay out {{math|''n'' + ''k'' − 1}} slots and choose {{math|''k'' − 1}} of these to contain bars (or, equivalently, choose ''n'' of the slots to contain stars).

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.

===Example===

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

When {{math|''n'' {{=}} 7}} and {{math|''k'' {{=}} 5}}, the tuple (4, 0, 1, 2, 0) may be represented by the following diagram:

{{image frame

|align=center

|content=

{{nowrap|{{huge|★ ★ ★ ★ &#124;{{pipe}} &#124;{{pipe}} ★ &#124;{{pipe}} ★ ★ &#124;{{pipe}}}}}}

|caption=Fig.&nbsp;3: These four bars give rise to five bins containing 4, 0, 1, 2, and 0 objects

}}

If possible bar positions are labeled 1, 2, 3, 4, 5, 6, 7, 8 with label {{math|''i '' ≤ ''7''}} corresponding to a bar preceding the {{mvar|i}}th star and following any previous star and 8 to a bar following the last star, then this configuration corresponds to the {{math|(''k'' − 1)}}-multiset {{math|{{mset|5,5,6,8}}}}, as described in the proof of Theorem two. If bins are labeled 1, 2, 3, 4, 5, then it also corresponds to the {{mvar|n}}-multiset {{math|{{mset|1,1,1,1,3,4,4}}}}, also as described in the proof of Theorem two.

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

==Relation between Theorems one and two==

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.

Theorem one can be restated in terms of Theorem two, because the requirement that each variable be positive can be imposed by shifting each variable by −1, and then requiring only that each variable be non-negative.

For example:

Line 80 ⟶ 102:

is equivalent to:

:<math>x_1x'_1+x_2x'_2+x_3x'_3+x_4x'_4=6</math>

with <math>x_1x'_1,x_2x'_2,x_3x'_3,x_4x'_4\ge0,</math>

where <math>x'_i = x_i - 1</math> for each <math>i\in\{1,2,3,4\}</math>.

==Proofs by generating functions==

==Further examples==

Both cases are very similar, we will look at the case when <math>x_i\ge0</math> first. The 'bucket' becomes

[[File:Colored circle starsbars 1.svg|thumb|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 [[c:Category:Counting colored circles|cookie-colored circles]] ({{color|#f4d8aaff|●●●●}}). The 3 gaps between the cookies are indicated by red [[carets]] ('''{{red|^&nbsp;^&nbsp;^}}'''). With three people, we need two bar symbols ('''<nowiki>|</nowiki>&nbsp;<nowiki>|</nowiki>''') to occupy any two of the three gaps. Hence the problem reduces to finding the binomial coefficient <math>\tbinom 3 2.</math> Also shown are the three corresponding [[Composition (combinatorics)|3-compositions of 4]].]]

[[File:Stars bars 5 take 2.svg|thumb|The three-choose-two combination yields two results, depending on whether a bin is allowed to have zero items. In both results the number of bins is 3. If zero is not allowed, the number of cookies should be {{math|1=''n'' = 6}}, as described in the previous figure. If zero is allowed, the number of cookies should only be {{math|1=''n'' = 3}}.]]

===Example 1===

:<math>\frac{1}{1-x}</math>

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 Theorem 1 applies, with {{math|1=''n'' = 7}} and {{math|1=''k'' = 3}}, and there are <math>\tbinom{7-1}{3-1} = 15</math> ways to distribute the coins.

===Example 2===

This can also be written as

If {{math|1=''n'' = 5}}, {{math|1=''k'' = 4}}, and the {{mvar|k}} bin labels are {{math|''a'', ''b'', ''c'', ''d''}}, then ★|★★★||★ could represent either the 4-[[tuple]] {{math|(1, 3, 0, 1)}}, or the multiset of bar positions {{math|{{mset|2, 5, 5}}}}, or the multiset of bin labels {{math|{{mset|''a'', ''b'', ''b'', ''b'', ''d''}}}}. The solution of this problem should use Theorem 2 with {{math|1=''n'' = 5}} stars and {{math|1=''k'' – 1 = 3}} bars to give <math>\tbinom{5+4-1}{4-1} = \tbinom{8}{3} = 56</math> configurations.

===Example 3===

:<math>1+x+x^2+\dots</math>

In the proof of Theorem two there can be more bars than stars, which cannot happen in the proof of Theorem one.

So, for example, 10 balls into 7 bins gives <math>\tbinom{16}{6}</math> configurations, while 7 balls into 10 bins gives <math>\tbinom{16}{9}</math> configurations, and 6 balls into 11 bins gives <math>\tbinom{16}{10}=\tbinom{16}{6}</math> configurations.

and the exponent of {{mvar|x}} tells us how many balls are placed in the bucket.

===Example 4===

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

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.<ref>{{cite journal |last1=Ehrenfest |first1=Paul |last2=Kamerlingh Onnes |first2=Heike |title=Simplified deduction of the formula from the theory of combinations which Planck uses as the basis of his radiation theory | journal = Proceedings of the KNAW | volume=17 | date = 1914 | pages = 870–873 | url = https://dwc.knaw.nl/toegangen/digital-library-knaw/?pagetype=publDetail&pId=PU00012735 | access-date = 16 May 2024}}</ref><ref>{{cite journal |last1=Ehrenfest |first1=Paul |last2=Kamerlingh Onnes |first2=Heike |title=Simplified deduction of the formula from the theory of combinations which Planck uses as the basis of his radiation theory |journal=The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science |series=Series 6 |date=1915 |volume=29 |issue=170 |pages=297–301 |doi=10.1080/14786440208635308 |url=http://dx.doi.org/10.1080/14786440208635308 |access-date=5 December 2020}}</ref>

By complexions ([[Microstate (statistical mechanics)|microstates]]) Planck meant distributions of {{mvar|P}} energy elements '''ε''' over {{mvar|N}} resonators.<ref>{{cite journal |last1=Planck |first1=Max |title=Ueber das Gesetz der Energieverteilung im Normalspectrum |journal=Annalen der Physik |date=1901 |volume=309 |issue=3 |pages=553–563 |doi=10.1002/andp.19013090310 |bibcode=1901AnP...309..553P |doi-access=free }}</ref><ref>{{cite journal | last = Gearhart | first = C. | title = Planck, the Quantum, and the Historians | journal = Phys. Perspect. | volume = 4 |pages = 170–215 | date = 2002 | issue = 2 |doi = 10.1007/s00016-002-8363-7 | bibcode = 2002PhP.....4..170G | url = https://employees.csbsju.edu/cgearhart/planck/pqh.pdf | access-date = 16 May 2024}}</ref> The number {{mvar|R}} of complexions is

:<math>\frac{1}{1-x}\frac{1}{1-x}\dots\frac{1}{1-x} = \frac{1}{(1-x)^k}</math>

:<math>R=\frac {(N+P-1)!}{P!(N-1)!}. \ </math>

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

As we only have {{mvar|n}} balls, we want the coefficient of <math>x^n</math> (written <math>[x^n]:</math>) from this

'''εεεε0εε00ε'''.

==Relation to generating functions==

:<math>[x^n]: \frac{1}{(1-x)^k}</math>

The enumerations of Theorems one and two can also be found using [[generating function]]s involving simple rational expressions. The two cases are very similar; we will look at the case when <math>x_i\ge0</math>, that is, Theorem two first. There is only one configuration for a single bin and any given number of objects (because the objects are not distinguished). This is represented by the generating function

:<math>1+1x+1x^2+1x^3+\ldots = 1+x+x^2+x^3+\ldots = \frac{1}{1-x}.</math>

This is a well-known generating function - it generates the diagonals in [[Pascal's Triangle]], and the coefficient of <math>x^n</math> is

The series is a geometric series, and the last equality holds analytically for {{math|{{abs|''x''}} < 1}}, but is better understood in this context as a manipulation of [[formal power series]]. The exponent of {{mvar|x}} indicates how many objects are placed in the bin.

:<math>\binom{n+k-1}{k-1}</math>

Each additional bin is represented by another factor of <math>\frac{1}{1-x}</math>; the generating function for {{mvar|k}} bins is

For the case when <math>x_i>0</math>, we need to add {{mvar|x}} into the numerator to indicate that at least one ball is in the bucket.

:<math>\underbrace{\frac{x1}{1-x}\frac{x1}{1-x}\dots\frac{x1}{1-x}}_{k\text{ factors}} = \frac{x^k1}{(1-x)^k}</math>,

where the multiplication is the [[Cauchy product]] of formal power series.

and the coefficient of <math>x^n</math> is

To find the number of configurations with {{mvar|n}} objects, we want the coefficient of <math>x^n</math> (denoted by prefixing the expression for the generating function with <math>[x^n]</math>), that is,

:<math>\binom{n-1}{k-1}</math>

:<math>[x^n]\frac{1}{(1-x)^k} = [x^n](1-x)^{-k}</math>.

==Examples==

Many elementary [[word problem (mathematics education)|word problems]] in combinatorics are resolved by the theorems above.

[[File:Colored circle starsbars 1.svg|thumb|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 [[c:Category:Counting colored circles|cookie-colored circles]] ({{color|#f4d8aaff|●●●●}}). The 3 gaps between the cookies are indicated by red [[carets]] ('''{{red|^&nbsp;^&nbsp;^}}'''). With three people, we need 2 bar symbols ('''<nowiki>|</nowiki>&nbsp;<nowiki>|</nowiki>''') to occupy any two of the three gaps. Hence the problem reduces to finding the binomial coefficient <math>\tbinom 3 2.</math> Also shown are the three corresponding [[Composition (combinatorics)|3-compositions of 4]].]]

[[File:Stars bars 5 take 2.svg|thumb|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 {{math|1=''n'' = 6}}, as described in the previous figure. If zero is allowed, the number of cookies is only {{math|1=''n'' = 3}}.]]

===Example 1===

This coefficient can be found using [[binomial series]] and agrees with the result of Theorem two, namely <math>\tbinom{n+k-1}{k-1}</math>.

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 {{math|1=''n'' = 7}} and {{math|1=''k'' = 3}}, and there are <math>\tbinom{7-1}{3-1} = 15</math> ways to distribute the coins.

This Cauchy product expression is justified via stars and bars: the coefficient of <math>x^n</math> in the expansion of the product

===Example 2===

:<math>\underbrace{(1+x+x^2+\ldots)(1+x+x^2+\ldots)\ldots(1+x+x^2+\ldots)}_{k\text{ factors}}</math>

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

is the number of ways of obtaining the {{mvar|n}}th power of {{mvar|x}} by multiplying one power of {{mvar|x}} from each of the {{mvar|k}} factors. So the stars represent {{mvar|x}}s and a bar separates the {{mvar|x}}s coming from one factor from those coming from the next factor.

===Example 3===

For the case when <math>x_i>0</math>, that is, Theorem one, no configuration has an empty bin, and so the generating function for a single bin is

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

:<math>x+x^2+x^3+\ldots = \frac{x}{1-x}</math>.

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

The Cauchy product is therefore <math>\frac{x^k}{(1-x)^k}</math>, and the coefficient of <math>x^n</math> is found using binomial series to be <math>\tbinom{n-1}{k-1}</math>.

=== Example 4 ===

If we have the infinite [[power series]]

:<math>\left[\sum_{k=1}^{\infty}x^k\right],</math>

we can use this method to compute the [[Cauchy product]] of {{mvar|m}} copies of the series. For the {{mvar|n}}th term of the expansion, we are picking {{mvar|n}} powers of {{mvar|x}} from m separate locations. Hence there are <math>\tbinom{n-1}{m-1}</math> ways to form our {{mvar|n}}th power:

:<math>\left[\sum_{k=1}^{\infty}x^k\right]^{m} = \sum_{n=m}^{\infty}{{n-1} \choose {m-1}}x^{n}

</math>

===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.<ref>{{cite journal |last1=Ehrenfest |first1=Paul |last2=Kamerlingh Onnes |first2=Heike |title=Simplified deduction of the formula from the theory of combinations which Planck uses as the basis of his radiation theory | journal = Proceedings of the KNAW | volume=17 | date = 1914 | pages = 870–873 | url = https://dwc.knaw.nl/toegangen/digital-library-knaw/?pagetype=publDetail&pId=PU00012735 | access-date = 16 May 2024}}</ref><ref>{{cite journal |last1=Ehrenfest |first1=Paul |last2=Kamerlingh Onnes |first2=Heike |title=Simplified deduction of the formula from the theory of combinations which Planck uses as the basis of his radiation theory |journal=The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science |series=Series 6 |date=1915 |volume=29 |issue=170 |pages=297–301 |doi=10.1080/14786440208635308 |url=http://dx.doi.org/10.1080/14786440208635308 |access-date=5 December 2020}}</ref>

By complexions ([[Microstate (statistical mechanics)|microstates]]) Planck meant distributions of {{mvar|P}} energy elements '''ε''' over {{mvar|N}} resonators.<ref>{{cite journal |last1=Planck |first1=Max |title=Ueber das Gesetz der Energieverteilung im Normalspectrum |journal=Annalen der Physik |date=1901 |volume=309 |issue=3 |pages=553–563 |doi=10.1002/andp.19013090310 |bibcode=1901AnP...309..553P |doi-access=free }}</ref><ref>{{cite journal | last = Gearhart | first = C. | title = Planck, the Quantum, and the Historians | journal = Phys. Perspect. | volume = 4 |pages = 170–215 | date = 2002 | issue = 2 |doi = 10.1007/s00016-002-8363-7 | bibcode = 2002PhP.....4..170G | url = https://employees.csbsju.edu/cgearhart/planck/pqh.pdf | access-date = 16 May 2024}}</ref> The number {{mvar|R}} of complexions is

:<math>R=\frac {(N+P-1)!}{P!(N-1)!}. \ </math>

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

'''εεεε0εε00ε'''.

==See also==