Content deleted Content added
m replaced the word "simple" with "a variety of". This is often covered in a 2nd semester university discrete math course, which means many students would not consider it simple. |
Will Orrick (talk | contribs) m Reverted 1 edit by 2402:E000:4BC:3535:60C5:63FF:FEE1:3289 (talk) to last revision by TonySt |
||
| (14 intermediate revisions by 11 users not shown) | |||
Line 5:
If, for example, there are two balls and three bins, then the number of ways of placing the balls is <math>\tbinom{2+3-1}{3-1} = \tbinom{4}{2} = 6</math>. The table shows the six possible ways of distributing the two balls, the strings of stars and bars that represent them (with stars indicating balls and bars separating bins from one another), and the subsets that correspond to the strings. As two bars are needed to separate three bins and there are two balls, each string contains two bars and two stars. Each subset indicates which of the four symbols in the corresponding string is a bar.
{| class="wikitable"
|+ Six configurations of two balls in three bins and their star and bar
|-
! Bin 1 !! Bin 2 !! Bin 3 !! String !! Subset of {1,2,3,4}
|-
| 2 || 0 || 0 || ★ ★
|-
| 1 || 1 || 0 || ★
|-
| 1 || 0 || 1 || ★
|-
| 0 || 2 || 0 ||
|-
| 0 || 1 || 1 ||
|-
| 0 || 0 || 2 ||
|}
Line 42:
where the [[Multiset#Counting multisets|multiset coefficient]] <math>\left(\!\!\binom{k}{n}\!\!\right)</math> is the number of multisets of size {{mvar|n}}, with elements taken from a set of size {{mvar|k}}.
This corresponds to [[Composition (combinatorics)|weak compositions]] of an integer. With {{mvar|k}} fixed, the numbers for {{math|''n'' {{=}} 0, 1, 2, 3,
==Proofs via the method of stars and bars==
Line 66:
|align=center
|content=
{{nowrap|{{huge|★ ★ ★ ★
|caption=Fig. 2: These two bars give rise to three bins containing 4, 1, and 2 objects
}}
Line 86:
|align=center
|content=
{{nowrap|{{huge|★ ★ ★ ★
|caption=Fig. 3: These four bars give rise to five bins containing 4, 0, 1, 2, and 0 objects
}}
| |||