Stars and bars (combinatorics)
   HOME

TheInfoList



OR:

In the context of
combinatorial mathematics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
, stars and bars (also called "sticks and stones", "balls and bars", and "dots and dividers") is a graphical aid for deriving certain
combinatorial Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
theorems. It was popularized by
William Feller William "Vilim" Feller (July 7, 1906 – January 14, 1970), born Vilibald Srećko Feller, was a Croatian- American mathematician specializing in probability theory. Early life and education Feller was born in Zagreb to Ida Oemichen-Perc, a Cro ...
in his classic book on
probability Probability is the branch of mathematics concerning numerical descriptions of how likely an Event (probability theory), event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and ...
. It can be used to solve many simple counting problems, such as how many ways there are to put indistinguishable balls into distinguishable bins.


Statements of theorems

The stars and bars method is often introduced specifically to prove the following two theorems of elementary combinatorics concerning the number of solutions to an equation.


Theorem one

For any pair of positive integers and , the number of -
tuple In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
s of positive integers whose sum is is equal to the number of -element subsets of a set with elements. For example, if and , the theorem gives the number of solutions to (with ) as the
binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
:\binom = \binom = \binom = 84.


Theorem two

For any pair of positive integers and , the number of -
tuple In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
s of non-negative integers whose sum is is equal to the number of
multiset In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
s of
cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
taken from a set of size , or equivalently, the number of multisets of cardinality taken from a set of size . For example, if and , the theorem gives the number of solutions to (with ) as: :\left(\!\!\!\!\right) = = \binom = 286 :\left(\!\!\!\!\right) = = \binom = 286 :\binom = \binom = \binom = 286


Proofs via the method of stars and bars


Theorem one proof

Suppose there are ''n'' objects (represented here by stars) to be placed into ''k'' bins, such that all bins contain at least one object. 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). A configuration is thus represented by a ''k''-tuple of positive integers, as in the statement of the theorem. For example, with and , start by placing the stars in a line: 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 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: There are gaps between stars. A configuration is obtained by choosing of these gaps to contain a bar; therefore there are \tbinom possible
combinations In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are t ...
.


Theorem two proof

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 and , the tuple (4, 0, 1, 2, 0) may be represented by the following diagram: To see that there are \tbinom 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). 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. For example: :x_1+x_2+x_3+x_4=10 with x_1,x_2,x_3,x_4>0 is equivalent to: :x_1+x_2+x_3+x_4=6 with x_1,x_2,x_3,x_4\ge0


Proofs by generating functions

Both cases are very similar, we will look at the case when x_i\ge0 first. The 'bucket' becomes :\frac This can also be written as :1+x+x^2+\dots and the exponent of tells us how many balls are placed in the bucket. Each additional bucket is represented by another \frac, and so the final generating function is :\frac\frac\dots\frac = \frac As we only have balls, we want the coefficient of x^m (written ^m) from this : ^m \frac This is a well-known generating function - it generates the diagonals in
Pascal's Triangle In mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although o ...
, and the coefficient of x^m is :\binom For the case when x_i>0, we need to add into the numerator to indicate that at least one ball is in the bucket. :\frac\frac\dots\frac = \frac and the coefficient of x^m is :\binom


Examples

Many elementary word problems in combinatorics are resolved by the theorems above.


Example 1

If one wishes to count the number of ways to distribute seven indistinguishable one dollar coins among Amber, Ben, and Curtis so that each of them receives at least one dollar, one may observe that distributions are essentially equivalent to tuples of three positive integers whose sum is 7. (Here the first entry in the tuple is the number of coins given to Amber, and so on.) Thus stars and bars theorem 1 applies, with and , and there are \tbinom = 15 ways to distribute the coins.


Example 2

If , , and a set of size is then ★, ★★★, , ★ could represent either the multiset or the 4-
tuple In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
The representation of any multiset for this example should use SAB2 with , bars to give \tbinom = \tbinom = 56.


Example 3

SAB2 allows for more bars than stars, which isn't permitted in SAB1. So, for example, 10 balls into 7 bins is \tbinom, while 7 balls into 10 bins is \tbinom, with 6 balls into 11 bins as \tbinom=\tbinom.


Example 4

If we have the infinite
power series In mathematics, a power series (in one variable) is an infinite series of the form \sum_^\infty a_n \left(x - c\right)^n = a_0 + a_1 (x - c) + a_2 (x - c)^2 + \dots where ''an'' represents the coefficient of the ''n''th term and ''c'' is a const ...
:\left sum_^x^k\right we can use this method to compute the
Cauchy product In mathematics, more specifically in mathematical analysis, the Cauchy product is the discrete convolution of two infinite series. It is named after the French mathematician Augustin-Louis Cauchy. Definitions The Cauchy product may apply to infini ...
of copies of the series. For the th term of the expansion, we are picking powers of from m separate locations. Hence there are \tbinom ways to form our th power: :\left sum_^x^k\right = \sum_^x^


Example 5

The graphical method was used by
Paul Ehrenfest Paul Ehrenfest (18 January 1880 – 25 September 1933) was an Austrian theoretical physicist, who made major contributions to the field of statistical mechanics and its relations with quantum mechanics, including the theory of phase transition a ...
and
Heike Kamerlingh Onnes Heike Kamerlingh Onnes (21 September 1853 – 21 February 1926) was a Dutch physicist and Nobel laureate. He exploited the Hampson–Linde cycle to investigate how materials behave when cooled to nearly absolute zero and later to liquefy heliu ...
– with symbol ε (quantum energy element) in place of a star – as a simple derivation of
Max Planck Max Karl Ernst Ludwig Planck (, ; 23 April 1858 – 4 October 1947) was a German theoretical physicist whose discovery of energy quanta won him the Nobel Prize in Physics in 1918. Planck made many substantial contributions to theoretical p ...
's expression of "complexions". Planck called "complexions" the number of possible distributions of energy elements ε over resonators: :R=\frac \ The graphical representation would contain times the symbol ε and times the sign , for each possible distribution. In their demonstration, Ehrenfest and Kamerlingh Onnes took and (''i.e.'', combinations). They chose the 4-tuple (4, 2, 0, 1) as the illustrative example for this symbolic representation: εεεε, εε, , ε


See also

*
Gaussian binomial coefficient In mathematics, the Gaussian binomial coefficients (also called Gaussian coefficients, Gaussian polynomials, or ''q''-binomial coefficients) are ''q''-analogs of the binomial coefficients. The Gaussian binomial coefficient, written as \binom n ...
*
Partition (number theory) In number theory and combinatorics, a partition of a positive integer , also called an integer partition, is a way of writing as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same parti ...
*
Twelvefold way In combinatorics, the twelvefold way is a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of counting permutations, combinations, multisets, and partitions either of a ...


References


Further reading

* *{{cite web, last=Weisstein, first=Eric W. , title=Multichoose , work=Mathworld -- A Wolfram Web Resource , url=http://mathworld.wolfram.com/Multichoose.html , accessdate=18 November 2012 Stars and bars (probability) Stars and bars (probability) Articles containing proofs