Stars and bars (combinatorics): Difference between revisions

Revision as of 23:09, 7 December 2024

Revision as of 16:38, 8 December 2024

Line 4:

==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>\binomtbinom{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>

Line 24 ⟶ 21:

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(\!\!{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\choose }{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, ….

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

Line 54 ⟶ 51:

}}

In general two of the six possible bar positions must be chosen. Therefore there are <math>\binomtbinom{6}{2} = 15</math> such configurations.

Line 76 ⟶ 73:

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

===Relation between Theorems one and two===

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.

Line 91 ⟶ 88:

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

==Further examples==

==Proofs by generating functions==

[[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 2two 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 casesresults the number of bins is 3. If zero is not allowed, the number of cookies isshould be {{math|1=''n'' = 6}}, as described in the previous figure. If zero is allowed, the number of cookies isshould only be {{math|1=''n'' = 3}}.]]

===Example 1===

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

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 theoremTheorem 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===

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

If {{math|1=''n'' = 5}}, {{math|1=''k'' = 4}}, and a set of sizethe {{mvar|k}} isbin labels are {{math|{''a'', ''b'', ''c'', ''d},''}}, then ★|★★★||★ could represent either the multiset4-[[tuple]] {{math|{a(1, b3, b0, b1)}}, d}or the multiset of bar positions {{math|{{mset|1, 4, 4}}}}, or the 4-[[tuple]]multiset of bin labels {{math|(1{{mset|''a'', 3''b'', 0''b'', 1).''b'', ''d''}}}}. The representationsolution of any multiset for this exampleproblem should use SAB2Theorem 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===

This can also be written as

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.

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

===Example 54===

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

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

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

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

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

==ProofsRelation byto generating functions==

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

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^n]:2+x^3+\ldots = \frac{1}{(1-x)^k}.</math>

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.

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

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

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

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

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.

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

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

AsTo wefind the number of onlyconfigurations havewith {{mvar|n}} ballsobjects, we want the coefficient of <math>x^n</math> (writtendenoted by prefixing the expression for the generating function with <math>[x^n]:</math>), fromthat thisis,

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

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

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>.

==Examples==

Many elementary [[Word problem (mathematics)|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 Cauchy product expression is justified via stars and bars: the coefficient of <math>x^n</math> in the expansion of the product

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.

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

===Example 2===

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.

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>.

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

===Example 3===

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

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

So,The forCauchy example,product 10is balls into 7 bins istherefore <math>\tbinomfrac{16x^k}{6(1-x)^k}</math>, whileand 7the ballscoefficient into 10 bins isof <math>\tbinom{16}{9}x^n</math>, withis 6found ballsusing intobinomial 11series binsto asbe <math>\tbinom{16n-1}{10k-1}=\tbinom{16}{6}.</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==