In combinatorics, stars and bars (also called sticks and stones, balls and bars, and dots and dividers) is a graphical aid for deriving certain combinatorial theorems. It can be used to solve a variety of counting problems, such as how many ways there are to put n indistinguishable balls into k distinguishable bins. The solution to this particular problem is given by the binomial coefficient ( n + k − 1 k − 1 ) {\displaystyle {\tbinom {n+k-1}{k-1}}} , which is the number of subsets of size k − 1 that can be formed from a set of size n + k − 1. If, for example, there are two balls and three bins, then the number of ways of placing the balls is ( 2 + 3 − 1 3 − 1 ) = ( 4 2 ) = 6 {\displaystyle {\tbinom {2+3-1}{3-1}}={\tbinom {4}{2}}=6} . The table shows the six possible ways of distributing the two balls, the strings of stars and bars that represent them (with stars indicating balls and bars separating bins from one another), and the subsets that correspond to the strings. As two bars are needed to separate three bins and there are two balls, each string contains two bars and two stars. Each subset indicates which of the four symbols in the corresponding string is a bar.
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 n and k, the number of k-tuples of positive integers whose sum is n is equal to the number of (k − 1)-element subsets of a set with n − 1 elements. For example, if n = 10 and k = 4, the theorem gives the number of solutions to x1 + x2 + x3 + x4 = 10 (with x1, x2, x3, x4 > 0) as the binomial coefficient
( n − 1 k − 1 ) = ( 10 − 1 4 − 1 ) = ( 9 3 ) = 84 , {\displaystyle {\binom {n-1}{k-1}}={\binom {10-1}{4-1}}={\binom {9}{3}}=84,}
where ( n − 1 k − 1 ) {\displaystyle {\tbinom {n-1}{k-1}}} is the number of combinations of n − 1 elements taken k − 1 at a time. This corresponds to compositions of an integer.
Theorem two For any pair of positive integers n and k, the number of k-tuples of non-negative integers whose sum is n is equal to the number of multisets of size k − 1 taken from a set of size n + 1, or equivalently, the number of multisets of size n taken from a set of size k, and is given by
( n + k − 1 k − 1 ) . {\displaystyle {\binom {n+k-1}{k-1}}.}
For example, if n = 10 and k = 4, the theorem gives the number of solutions to x1 + x2 + x3 + x4 = 10 (with x1, x2, x3, x4 ≥ 0 {\displaystyle \geq 0} ) as
… excerpt ends here. Continue reading the full article.
