Maths WorkshopMaths problems with full solutions
Exercise 335Combinatorics › Counting principlesL1Added 31 Oct 2026

Stars and bars

#counting#equations

Statement

How many triples (x,y,z)(x,y,z) of non-negative integers satisfy x+y+z=10x+y+z=10? How many if x,y,zx,y,z must be positive?

Hint

Represent a solution as 1010 stars separated by 22 bars.

Show solutionHide solution

Solution

A solution corresponds to a row of 1010 stars and 22 bars: the stars before the first bar count xx, those between the bars count yy, those after the second bar count zz. A row has 1212 positions, and we choose which 22 are bars. The number of non-negative solutions is
(122)=66.\binom{12}{2}=66.

For positive solutions, set x′=x−1x'=x-1, y′=y−1y'=y-1, z′=z−1≥0z'=z-1\ge0. Then x′+y′+z′=7x'+y'+z'=7, which has (92)=36\binom{9}{2}=36 non-negative solutions.