Exercise 335Combinatorics › Counting principlesL1Added 31 Oct 2026
Stars and bars
#counting#equations
Statement
How many triples of non-negative integers satisfy ? How many if must be positive?
Hint
Represent a solution as stars separated by bars.
Show solutionHide solution
Solution
A solution corresponds to a row of stars and bars: the stars before the first bar count , those between the bars count , those after the second bar count . A row has positions, and we choose which are bars. The number of non-negative solutions is
For positive solutions, set , , . Then , which has non-negative solutions.