Stars and bars (combinatorics): Difference between revisions

Revision as of 14:39, 16 August 2024

Revision as of 15:05, 15 October 2024

Line 116:

==Examples==

Many elementary [[wordWord 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}}.]]