Stars and bars (combinatorics): Difference between revisions

Revision as of 15:30, 6 December 2024

Revision as of 16:31, 6 December 2024

Line 14:

For example, if {{math|1=''n'' = 10}} and {{math|1=''k'' = 4}}, the theorem gives the number of solutions to {{math|1=''x''{{sub|1}} + ''x''{{sub|2}} + ''x''{{sub|3}} + ''x''{{sub|4}} = 10}} (with {{math|''x''{{sub|1}}, ''x''{{sub|2}}, ''x''{{sub|3}}, ''x''{{sub|4}} > 0}}) as the [[binomial coefficient]]

:<math>\binom{n - 1}{k - 1} = \binom{10 - 1}{4 - 1} = \binom{9}{3} = 84.,</math>

where <math>\binom{n - 1}{k - 1}</math> is the number of [[combination]]s of {{math|''n'' − 1}} elements taken {{math|''k'' − 1}} at a time.

This corresponds to [[Composition (combinatorics)|compositions]] of an integer.

Line 32 ⟶ 33:

===Theorem one proof===

SupposeThe thereproblem areof enumerating ''k''-tuples whose sum is ''n'' objectsis (representedequivalent hereto bythe stars)problem of counting configurations of the following kind: let there be ''n'' objects to be placed into ''k'' bins, suchso that all bins contain at least one object. The bins are distinguishabledistinguished (say they are numbered 1 to ''k'') but the ''n'' starsobjects are not (so configurations are only distinguished by the ''number of starsobjects'' present in each bin). A configuration is thus represented by a ''k''-tuple of positive integers, as in the statement of the theorem.

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.

For example, with {{math|''n'' {{=}} 7}} and {{math|''k'' {{=}} 3}}, start by placing the stars in a line:

===Example===

For example, withWith {{math|''n'' {{=}} 7}} and {{math|''k'' {{=}} 3}}, start by placing theseven stars in a line:

{{image frame

Line 43 ⟶ 47:

}}

Now indicate the boundaries between the bins:

The configuration will be determined once it is known which is the first star going to the second bin, and the first star going to the third bin, etc.. This is indicated by placing {{math|''k'' − 1}} bars between the stars. Because no bin is allowed to be empty (all the variables are positive), there is at most one bar between any pair of stars.

For example:

{{image frame

Line 54 ⟶ 56:

}}

In general two of the six possible bar positions must be chosen. Therefore there are <math>\binom{6}{2} = 15</math> such configurations.

There are {{math|''n'' − 1}} gaps between stars. 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> possible [[combinations]].

===Theorem two proof===