Stars and bars (combinatorics): Difference between revisions

Revision as of 00:04, 20 April 2024

Revision as of 21:01, 15 May 2024

Line 1:

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

In the context of [[combinatorial mathematics]], '''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 was popularized by [[William Feller]] in his classic book on [[probability]]. 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=19501968 |title=An Introduction to Probability Theory and Its Applications |publisher=Wiley |volume=1 |edition=3rd |page=38}}</ref>

==Statements of theorems==