Content deleted Content added
Will Orrick (talk | contribs) →Proofs via the method of stars and bars: Revised proof of Theorem 2: the theorem statement talks about multisets, so this needed to be addressed in the proof; also added relation to the object-bin model; separated example from proof and sharpened relation between Theorem 1 and Theorem 2 |
Will Orrick (talk | contribs) Reorder statements in Theorem two to match what's in the proof. Typo corrections. Elaborate on different multiset interpretations and how this corresponds to interchanging bars and stars. |
||
Line 21:
===Theorem two===
For any pair of positive integers {{mvar|n}} and {{mvar|k}}, the number of {{mvar|k}}-[[tuple]]s of '''non-negative''' integers whose sum is {{mvar|n}} is equal to the number of
For example, if {{math|1=''n'' = 10}} and {{math|1=''k'' = 4}}, the theorem gives the number of solutions to {{math|1=''x''{{sub|1}} + ''x''{{sub|2}} + ''x''{{sub|3}} + ''x''{{sub|4}} = 10}} (with {{math|''x''{{sub|1}}, ''x''{{sub|2}}, ''x''{{sub|3}}, ''x''{{sub|4}} <math>\ge0</math> }}) as:
:<math>\left(\!\!{k\choose n}\!\!\right) = {k+n-1 \choose n} = \binom{13}{10} = 286</math>▼
:<math>\left(\!\!{n+1\choose k-1}\!\!\right) = {n+1+k-1-1 \choose k-1} = \binom{13}{3} = 286</math>
▲:<math>\left(\!\!{k\choose n}\!\!\right) = {k+n-1 \choose n} = \binom{13}{10} = 286</math>
:<math>\binom{n + k - 1}{k - 1} = \binom{10+4-1}{4 - 1} = \binom{13}{3} = 286</math>
Line 64:
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
===Example===
| |||