Stars and bars (combinatorics): Difference between revisions

Revision as of 07:40, 5 June 2024

Revision as of 12:30, 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:

{{image frame

To see that there are possible arrangements, observe that any arrangement of stars and bars consists of a total of objects, ''n'' of which are stars and of which are bars. Thus, we only need to choose of the positions to be bars (or, equivalently, choose ''n'' of the positions to be stars).

|align=center

|content=

{{nowrap|{{huge|★ ★ ★ ★ | | ★ | ★ ★ |}}}}

|caption=Fig. 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 66 ⟶ 73:

For example:

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

:

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

with

is equivalent to:

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

:

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

with

==Proofs by generating functions==