Stars and bars (combinatorics): Difference between revisions

Revision as of 22:54, 8 December 2024

Latest revision as of 16:05, 19 August 2025

(20 intermediate revisions by 13 users not shown)

Line 1:

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

In [[combinatorics]], '''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.

{| class="wikitable"

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

|-

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

|-

| ★ ★ &#124; &#124;2 || 20 || 0 || 0★ ★ {{pipe}} {{pipe}} || {3,4}

|-

| ★ &#124; ★ &#124;1 || 1 || 10 || 0★ {{pipe}} ★ {{pipe}} || {2,4}

|-

| ★1 &#124;|| &#124; ★0 || 1 || 0★ ||{{pipe}} 1 {{pipe}} ★ || {2,3}

|-

| 0 &#124;|| ★ ★ &#124;2 || 0 || 2{{pipe}} ||★ 0★ {{pipe}} || {1,4}

|-

| &#124; ★ &#124; ★0 || 01 || 1 || 1{{pipe}} ★ {{pipe}} ★ || {1,3}

|-

| &#124; &#124; ★ ★0 || 0 || 02 || 2{{pipe}} {{pipe}} ★ ★ || {1,2}

|}

Line 42:

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

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

Line 66:

|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

}}

Line 86:

|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 0, 1, 2, 3, 4, 5, 6, 7, 8 with 0 corresponding to a bar to the left of the first star and positive label {{mvarmath|''i '' ≤ ''7''}} corresponding to a bar followingpreceding the {{mvar|i}}th star and precedingfollowing any subsequentprevious star and 8 to a bar following the last star, then this configuration corresponds to the {{math|(''k'' − 1)}}-multiset {{math|{{mset|4,45,5,76,8}}}}, as described in the proof of Theorem two. If bins are labeled 0, 1, 2, 3, 4, 5, then it also corresponds to the {{mvar|n}}-multiset {{math|{{mset|01,01,01,0,21,3,34,4}}}}, also as described in the proof of Theorem two.

==Relation between Theorems one and two==

Line 115:

===Example 2===

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|12, 45, 45}}}}, 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===