In the context of combinatorial mathematics, stars and bars (also called "sticks and stones",[1] "balls and bars",[2] and "dots and dividers"[3]) is a graphical aid for deriving certain combinatorial theorems. It can be used to solve many simple counting problems, such as how many ways there are to put indistinguishable balls into distinguishable bins.[4]
Theorems one and two are the coefficients used for 2 different support ranges in the negative binomial probability distribution.
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.
For any pair of positive integers and, the number of -tuples 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
\binom{n-1}{k-1}=\binom{10-1}{4-1}=\binom{9}{3}=84.
This corresponds to compositions of an integer.
For any pair of positive integers and, the number of -tuples of non-negative integers whose sum is is equal to the number of multisets of cardinality 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({k\choosen}\right)={k+n-1\choosen}=\binom{13}{10}=286
\left({n+1\choosek-1}\right)={n+1+k-1-1\choosek-1}=\binom{13}{3}=286
\binom{n+k-1}{k-1}=\binom{10+4-1}{4-1}=\binom{13}{3}=286
This corresponds to weak compositions of an integer.
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{n-1}{k-1}
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{n+k-1}{k-1}
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:
x1+x2+x3+x4=10
x1,x2,x3,x4>0
is equivalent to:
x1+x2+x3+x4=6
x1,x2,x3,x4\ge0
Both cases are very similar, we will look at the case when
xi\ge0
| 1 | |
| 1-x |
This can also be written as
1+x+x2+...
and the exponent of tells us how many balls are placed in the bucket.
Each additional bucket is represented by another
| 1 | |
| 1-x |
| 1 | |
| 1-x |
| 1 | ... | |
| 1-x |
| 1 | |
| 1-x |
=
| 1 | |
| (1-x)k |
As we only have balls, we want the coefficient of
xn
[xn]:
[xn]:
| 1 | |
| (1-x)k |
This is a well-known generating function - it generates the diagonals in Pascal's Triangle, and the coefficient of
xn
\binom{n+k-1}{k-1}
For the case when
xi>0
| x | |
| 1-x |
| x | ... | |
| 1-x |
| x | |
| 1-x |
=
| xk | |
| (1-x)k |
and the coefficient of
xn
\binom{n-1}{k-1}
Many elementary word problems in combinatorics are resolved by the theorems above.