^ Flajolet, Philippe Sedgewick, Robert (June 26, 2009).They chose the 4-tuple (4, 2, 0, 1) as the illustrative example for this symbolic representation: In their demonstration, Ehrenfest and Kamerlingh Onnes took N = 4 and P = 7 ( i.e., R = 120 combinations). The graphical representation would contain P times the symbol ε and N – 1 times the sign | for each possible 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.įor 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.įor 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 ( n − 1 k − 1 ) = ( 10 − 1 4 − 1 ) = ( 9 3 ) = 84. 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. It was popularized by William Feller in his classic book on probability. 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. Graphical aid for deriving some concepts in combinatorics
