Content deleted Content added
Will Orrick (talk | contribs) Revised statement and proof of Theorem 1: moved link to combinations article from the proof into the example following the theorem statement; separated the proof from the example; elaborated on the correspondence between the k-tuple problem and the counting problem with objects and bins; other wording changes. |
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 |
||
Line 60:
===Theorem two proof===
In this case, the weakened restriction of non-negativity instead of positivity means that we can place multiple bars between stars
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}}
▲In this case, the weakened restriction of non-negativity instead of positivity means that we can place multiple bars between stars, before the first star and after the last star.
Rather than a {{math|(''k'' − 1)}}-set of bar positions taken from a set of size as {{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 as {{math|(''n'' + 1)}} (since bar positions may repeat and since the ends are now allowed bar positions). There is an alternative interpretation in terms of multisets: 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 indicates the number of objects placed in that bin.)
For example, when {{math|''n'' {{=}} 7}} and {{math|''k'' {{=}} 5}}, the tuple (4, 0, 1, 2, 0) may be represented by the following diagram:▼
===Example===
▲
{{image frame
Line 72 ⟶ 76:
}}
===Relation between Theorems one and two===
▲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}} objects, ''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).
Theorem
▲Theorem 1 can now be restated in terms of Theorem 2, because the requirement that all the variables are positive is equivalent to pre-assigning each variable a ''1'', and asking for the number of solutions when each variable is non-negative.
For example:
Line 83 ⟶ 86:
is equivalent to:
:<math>
with <math>
where <math>x'_i = x_i - 1</math> for each <math>i\in\{1,2,3,4\}</math>.
==Proofs by generating functions==
| |||