Content deleted Content added
Will Orrick (talk | contribs) Make "Relation between Theorems one and two" its own section. "Examples" --> "Further examples" and make some wording changes. Rm remark about "word problems", which was mislinked. Merge Example 4 into section on generating functions, now at the end, and revise the exposition. Move remark about diagonals of Pascal's triangle to immediately follow Thm two. |
Will Orrick (talk | contribs) No edit summary |
||
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 many simple [[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}}
{| class="wikitable"
|+ Caption text
|-
! String !! Bin 1 !! Bin 2 !! Bin 3 !! Subset of {1,2,3,4}
|-
| ★ ★ | | || 2 || 0 || 0 || {3,4}
|-
| ★ | ★ | || 1 || 1 || 0 || {2,4}
|-
| ★ | | ★ || 1 || 0 || 1 || {2,3}
|-
| | ★ ★ | || 0 || 2 || 0 || {1,4}
|-
| | ★ | ★ || 0 || 1 || 1 || {1,3}
|-
| | | ★ ★ || 0 || 0 || 2 || {1,2}
|}
==Statements of theorems==
| |||