|
The ''n'' objects are now represented as a row of ''n'' stars; adjacent bins are separated by bars. The configuration will be specified by indicating the boundary between the first and second bin, the boundary between the second and third bin, and so on. Hence {{math|''k'' − 1}} bars need to be placed between stars. Because no bin is allowed to be empty, there is at most one bar between any pair of stars. There are {{math|''n'' − 1}} gaps between stars and hence {{math|''n'' − 1}} positions in which a bar may be placed. A configuration is obtained by choosing {{math|''k'' − 1}} of these gaps to contain a bar; therefore there are <math>\tbinom{n - 1}{k - 1}</math> configurations.
===Example===
With {{math|''n'' {{=}} 7}} and {{math|''k'' {{=}} 3}}, start by placing seven stars in a line:
{{image frame
|align=center
|content=
{{nowrap|{{huge|★ ★ ★ ★ ★ ★ ★}}}}
|caption=Fig. 1: Seven objects, represented by stars
}}
Now indicate the boundaries between the bins:
{{image frame
|align=center
|content=
{{nowrap|{{huge|★ ★ ★ ★ | ★ | ★ ★}}}}
|caption=Fig. 2: These two bars give rise to three bins containing 4, 1, and 2 objects
}}
In general two of the six possible bar positions must be chosen. Therefore there are <math>\tbinom{6}{2} = 15</math> such configurations.
===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.
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 the expression <math>\tbinom{n + k - 1}{k-1}</math> directly, 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 may lay out {{math|''n'' + ''k'' − 1}} slots and choose {{math|''k'' − 1}} of these to contain bars (or, equivalently, choose ''n'' of the slots to contain stars).
===Example===
When {{math|''n'' {{=}} 7}} and {{math|''k'' {{=}} 5}}, the tuple (4, 0, 1, 2, 0) may be represented by the following diagram:
{{image frame
|align=center
|content=
{{nowrap|{{huge|★ ★ ★ ★ | | ★ | ★ ★ |}}}}
|caption=Fig. 3: These four bars give rise to five bins containing 4, 0, 1, 2, and 0 objects
}}
If possible bar positions are labeled 1, 2, 3, 4, 5, 6, 7, 8 with label {{math|''i '' ≤ ''7''}} corresponding to a bar preceding the {{mvar|i}}th star and following any previous star and 8 to a bar following the last star, then this configuration corresponds to the {{math|(''k'' − 1)}}-multiset {{math|{{mset|5,5,6,8}}}}, as described in the proof of Theorem two. If bins are labeled 1, 2, 3, 4, 5, then it also corresponds to the {{mvar|n}}-multiset {{math|{{mset|1,1,1,1,3,4,4}}}}, also as described in the proof of Theorem two.==Proofs via the method of stars and bars==
===Theorem one proof===
The problem of enumerating ''k''-tuples whose sum is ''n'' is equivalent to the problem of counting configurations of the following kind: let there be ''n'' objects to be placed into ''k'' bins, so that all bins contain at least one object. The bins are distinguished (say they are numbered 1 to ''k'') but the ''n'' objects are not (so configurations are only distinguished by the ''number of objects'' present in each bin). A configuration is thus represented by a ''k''-tuple of positive integers.
The ''n'' objects are now represented as a row of ''n'' stars; adjacent bins are separated by bars. The configuration will be specified by indicating the boundary between the first and second bin, the boundary between the second and third bin, and so on. Hence {{math|''k'' − 1}} bars need to be placed between stars. Because no bin is allowed to be empty, there is at most one bar between any pair of stars. There are {{math|''n'' − 1}} gaps between stars and hence {{math|''n'' − 1}} positions in which a bar may be placed. A configuration is obtained by choosing {{math|''k'' − 1}} of these gaps to contain a bar; therefore there are <math>\tbinom{n - 1}{k - 1}</math> ==Proofs via the method of stars and bars==
===Theorem one proof===
The problem of enumerating ''k''-tuples whose sum is ''n'' is equivalent to the problem of counting configurations of the following kind: let there be ''n'' objects to be placed into ''k'' bins, so that all bins contain at least one object. The bins are distinguished (say they are numbered 1 to ''k'') but the ''n'' objects are not (so configurations are only distinguished by the ''number of objects'' present in each bin). A configuration is thus represented by a ''k''-tuple of positive integers.
The ''n'' objects are now represented as a row of ''n'' stars; adjacent bins are separated by bars. The configuration will be specified by indicating the boundary between the first and second bin, the boundary between the second and third bin, and so on. Hence {{math|''k'' − 1}} bars need to be placed between stars. Because no bin is allowed to be empty, there is at most one bar between any pair of stars. There are {{math|''n'' − 1}} gaps between stars and hence {{math|''n'' − 1}} positions in which a bar may be placed. A configuration is obtained by choosing {{math|''k'' − 1}} of these gaps to contain a bar; therefore there are <math>\tbinom{n - 1}{k - 1}</math> configurations.
===Example===
With {{math|''n'' {{=}} 7}} and {{math|''k'' {{=}} 3}}, start by placing seven stars in a line:
{{image frame
|align=center
|content=
{{nowrap|{{huge|★ ★ ★ ★ ★ ★ ★}}}}
|caption=Fig. 1: Seven objects, represented by stars
}}
Now indicate the boundaries between the bins:
{{image frame
|align=center
|content=
{{nowrap|{{huge|★ ★ ★ ★ | ★ | ★ ★}}}}
|caption=Fig. 2: These two bars give rise to three bins containing 4, 1, and 2 objects
}}
In general two of the six possible bar positions must be chosen. Therefore there are <math>\tbinom{6}{2} = 15</math> such configurations.
===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.
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 the expression <math>\tbinom{n + k - 1}{k-1}</math> directly, 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 may lay out {{math|''n'' + ''k'' − 1}} slots and choose {{math|''k'' − 1}} of these to contain bars (or, equivalently, choose ''n'' of the slots to contain stars).
===Example===
When {{math|''n'' {{=}} 7}} and {{math|''k'' {{=}} 5}}, the tuple (4, 0, 1, 2, 0) may be represented by the following diagram:
{{image frame
|align=center
|content=
{{nowrap|{{huge|★ ★ ★ ★ | | ★ | ★ ★ |}}}}
|caption=Fig. 3: These four bars give rise to five bins containing 4, 0, 1, 2, and 0 objects
}}
If possible bar positions are labeled 1, 2, 3, 4, 5, 6, 7, 8 with label {{math|''i '' ≤ ''7''}} corresponding to a bar preceding the {{mvar|i}}th star and following any previous star and 8 to a bar following the last star, then this configuration corresponds to the {{math|(''k'' − 1)}}-multiset {{math|{{mset|5,5,6,8}}}}, as described in the proof of Theorem two. If bins are labeled 1, 2, 3, 4, 5, then it also corresponds to the {{mvar|n}}-multiset {{math|{{mset|1,1,1,1,3,4,4}}}}, also as described in the proof of Theorem two..
===Example===
| 