Stars and bars (combinatorics): Difference between revisions

Revision as of 15:17, 16 May 2024

Revision as of 07:40, 5 June 2024

Line 58:

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.

For example, when {{math|''n'' {{=}} 7}} and {{math|''k'' {{=}} 5}}, the tuple (4, 0, 1, 2, 0) may be represented by the following diagram:

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).

{{image frame

|align=center

|content=

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

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

}}

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 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.

Line 73 ⟶ 66:

For example:

:

:<math>x_1+x_2+x_3+x_4=10</math>

with

with <math>x_1,x_2,x_3,x_4>0</math>

is equivalent to:

:

:<math>x_1+x_2+x_3+x_4=6</math>

with

with <math>x_1,x_2,x_3,x_4\ge0</math>

==Proofs by generating functions==