Stars and bars (combinatorics)

In the context of combinatorial mathematics, 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 was popularized by William Feller in his classic book on probability. 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. 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 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 x_1 + x_2 + x_3 + x_4 = 10 (with x_1, x_2, x_3, x_4 > 0) as the binomial coefficient This corresponds to compositions of an integer. 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 cardinality n taken from a set of size k, or equivalently, the number of multisets of cardinality k − 1 taken from a set of size n + 1. For example, if n = 10 and k = 4, the theorem gives the number of solutions to x_1 + x_2 + x_3 + x_4 = 10 (with x_1, x_2, x_3, x_4 ) as: 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 n = 7 and k = 3, 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.