Stars and bars (combinatorics): Difference between revisions

Revision as of 07:03, 22 February 2025

Revision as of 04:11, 26 February 2025

Line 9:

! Bin 1 !! Bin 2 !! Bin 3 !! String !! Subset of {1,2,3,4}

|-

| 2 || 0 || 0 || ★ ★ |{{pipe}} |{{pipe}} || {3,4}

|-

| 1 || 1 || 0 || ★ |{{pipe}} ★ |{{pipe}} || {2,4}

|-

| 1 || 0 || 1 || ★ |{{pipe}} |{{pipe}} ★ || {2,3}

|-

| 0 || 2 || 0 || |{{pipe}} ★ ★ |{{pipe}} || {1,4}

|-

| 0 || 1 || 1 || |{{pipe}} ★ |{{pipe}} ★ || {1,3}

|-

| 0 || 0 || 2 || |{{pipe}} |{{pipe}} ★ ★ || {1,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, …...}} are those in the {{math|(''k'' − 1)}}st diagonal of [[Pascal's triangle]]. For example, when {{math|''k'' {{=}} 3}} the {{mvar|n}}th number is the {{math|(''n'' + 1)}}st [[triangular number]], which falls on the second diagonal, 1, 3, 6, 10, …....

==Proofs via the method of stars and bars==

Line 66:

|align=center

|content=

{{nowrap|{{huge|★ ★ ★ ★ &#124;{{pipe}} ★ &#124;{{pipe}} ★ ★}}}}

|caption=Fig.&nbsp;2: These two bars give rise to three bins containing 4, 1, and 2 objects

}}

Line 86:

|align=center

|content=

{{nowrap|{{huge|★ ★ ★ ★ &#124;{{pipe}} &#124;{{pipe}} ★ &#124;{{pipe}} ★ ★ &#124;{{pipe}}}}}}

|caption=Fig.&nbsp;3: These four bars give rise to five bins containing 4, 0, 1, 2, and 0 objects

}}