Stars and bars (combinatorics)

From Wikipedia for FEVERv2
Jump to navigation Jump to search

In the context of combinatorial mathematics, stars and bars is a graphical aid for deriving certain combinatorial theorems. Stars and bars (combinatorics)_sentence_0

It was popularized by William Feller in his classic book on probability. Stars and bars (combinatorics)_sentence_1

It can be used to solve many simple counting problems, such as how many ways there are to put n indistinguishable balls into k distinguishable bins. Stars and bars (combinatorics)_sentence_2

Statements of theorems Stars and bars (combinatorics)_section_0

The stars and bars method is often introduced specifically to prove the following two theorems of elementary combinatorics. Stars and bars (combinatorics)_sentence_3

Theorem one Stars and bars (combinatorics)_section_1

Theorem two Stars and bars (combinatorics)_section_2

Proofs via the method of stars and bars Stars and bars (combinatorics)_section_3

Theorem one Stars and bars (combinatorics)_section_4

Suppose there are n objects (represented by stars; in the example below n = 7) to be placed into k bins (in the example k = 3), such that all bins contain at least one object. Stars and bars (combinatorics)_sentence_4

The bins are distinguishable (say they are numbered 1 to k) but the n stars are not (so configurations are only distinguished by the number of stars present in each bin). Stars and bars (combinatorics)_sentence_5

A configuration is thus represented by a k-tuple of positive integers, as in the statement of the theorem. Stars and bars (combinatorics)_sentence_6

Instead of starting by placing stars into bins, start by placing the stars on a line: Stars and bars (combinatorics)_sentence_7

where the stars for the first bin will be taken from the left, followed by the stars for the second bin, and so forth. Stars and bars (combinatorics)_sentence_8

Thus, 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, and so on. Stars and bars (combinatorics)_sentence_9

This can be indicated by placing k − 1 separating bars at places between two stars. Stars and bars (combinatorics)_sentence_10

Since no bin is allowed to be empty, there can be at most one bar between a given pair of stars: Stars and bars (combinatorics)_sentence_11

Theorem two Stars and bars (combinatorics)_section_5

In this case, the representation of a tuple as a sequence of stars and bars, with the bars dividing the stars into bins, is unchanged. Stars and bars (combinatorics)_sentence_12

The weakened restriction of nonnegativity (instead of positivity) means that one may place multiple bars between two stars, as well as placing bars before the first star or after the last star. Stars and bars (combinatorics)_sentence_13

Thus, for example, when n = 7 and k = 5, the tuple (4, 0, 1, 2, 0) may be represented by the following diagram. Stars and bars (combinatorics)_sentence_14

Examples Stars and bars (combinatorics)_section_6

Example 1 Stars and bars (combinatorics)_section_7

If n = 5, k = 4, and a set of size k is {a, b, c, d}, then ★|★★★||★ would represent the multiset {a, b, b, b, d} or the 4-tuple (1, 3, 0, 1). Stars and bars (combinatorics)_sentence_15

The representation of any multiset for this example would use n = 5 stars and k − 1 = 3 bars. Stars and bars (combinatorics)_sentence_16

Example 2 Stars and bars (combinatorics)_section_8

The graphical method was used by Paul Ehrenfest and Heike Kamerlingh Onnes – with symbol ε (quantum energy element) in place of a star – as a simple derivation of Max Planck’s expression of “complexions” . Stars and bars (combinatorics)_sentence_17

The graphical representation would contain P times the symbol “ε” and (N - 1) times the sign “|” for each possible distribution. Stars and bars (combinatorics)_sentence_18

In their demonstration, Ehrenfest and Kamerlingh Onnes took N = 4 and P = 7 (i.e., R = 120 combinations). Stars and bars (combinatorics)_sentence_19

They chose the 4-tuple (4, 2, 0, 1) as the illustrative example for this symbolic representation: εεεε|εε||ε Stars and bars (combinatorics)_sentence_20

See also Stars and bars (combinatorics)_section_9

Stars and bars (combinatorics)_unordered_list_0


Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Stars and bars (combinatorics).