Content deleted Content added
Will Orrick (talk | contribs) →Theorem two: missing "the"; "cardinality" --> "size" |
Will Orrick (talk | contribs) →Theorem two proof: Swapped second and third paragraphs of proof to match order in the statement of the theorem. Also, "position" was being used in different ways between the paragraphs, so I rephrased the now third paragraph using "slots" instead of positions. |
||
Line 59:
===Theorem two proof===
In this case, the weakened restriction of non-negativity instead of positivity means that we can place multiple bars between stars and that one or more bars also be placed before the first star and after the last star. In terms of configurations involving objects and bins, bins are now allowed to be empty.
To see that there are <math>\tbinom{n + k - 1}{k-1}</math> possible arrangements, observe that any arrangement of stars and bars consists of a total of {{math|''n'' + ''k'' − 1}} symbols, {{mvar|n}} of which are stars and {{math|''k'' − 1}} of which are bars. Thus, we only need to choose {{math|''k'' − 1}} of the {{math|''n'' + ''k'' − 1}} positions to be bars (or, equivalently, choose ''n'' of the positions to be stars).▼
Rather than a {{math|(''k'' − 1)}}-set of bar positions taken from a set of size {{math|''n'' − 1}} as in the proof of Theorem one, we now have a {{math|(''k'' − 1)}}-multiset of bar positions taken from a set of size {{math|''n'' + 1}} (since bar positions may repeat and since the ends are now allowed bar positions). An alternative interpretation in terms of multisets is the following: there is a set of {{mvar|k}} bin labels from which a multiset of size {{mvar|n}} is to be chosen, the multiplicity of a bin label in this multiset indicating the number of objects placed in that bin. The equality <math>\left(\!\!{n+1\choose k-1}\!\!\right) = \left(\!\!{k\choose n}\!\!\right)</math> can also be understood as an equivalence of different counting problems: the number of {{mvar|k}}-tuples of non-negative integers whose sum is {{mvar|n}} equals the number of {{math|(''n'' + 1)}}-tuples of non-negative integers whose sum is {{math|''k'' − 1}}, which follows by interchanging the roles of bars and stars in the diagrams representing configurations.
▲To see
===Example===
| |||