x₁ + x₂ + x₃ = 10, xᵢ ≥ 1
C(9, 2)
36.
The number of solutions of in positive integers is . With non-negative integers it is .
This page is easier if you are comfortable with:
Picture identical objects in a row, with gaps between them. To split them into non-empty groups, choose of the gaps to put dividers in: that is ways, a counting argument based on binomial coefficients. This is the "stars and bars" method.
If groups may be empty, add 1 to each variable: satisfies with each , giving . Other lower bounds are handled by shifting in the same way. For ordered choices see the product rule, and for circular seating see circular arrangements.
Applications include sharing sweets, counting terms of the form in an expansion (see the binomial theorem) and counting outcomes of dice sums. The same counts appear in the hockey-stick identity and in Vandermonde's identity.
Stars and bars counts the ways to share identical items among groups.
The counts are the triangular numbers 1, 3, 6, 10, 15, 21.
These examples are worked by hand, step by step, so you can compare your own working.
In how many ways can 10 identical sweets be given to 4 children, each getting at least one?
How many positive integer solutions has ?
How many non-negative integer solutions has ?
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
C(9, 2)
36.
C(12, 2)
66.
C(7, 3)
35.
C(11, 3)
165.
Positive integer solutions of x₁ + … + x_k = n number C(n − 1, k − 1); non-negative solutions number C(n + k − 1, k − 1).
x₁ + x₂ + x₃ = 10.
Same equation, xᵢ ≥ 0.
x₁ + … + x₄ = 8.
Same sum.
C(n+k−1, k−1) for positive ✗
C(n−1, k−1) ✓
Positive vs non-negative.
same ✗
identical only ✓
Stars identical.
C(n, k) ✗
C(…, k − 1) ✓
k − 1 bars.
unbounded ✗
extra bounds need inclusion–exclusion ✓
Upper bounds.
Try each one on paper, then open the answer. Use the solver above to see the full working.
21
45
165
84
1
6
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
C(n − 1, k − 1).
C(n + k − 1, k − 1).
Substitute yᵢ = xᵢ + 1.
No, identical.
circular arrangements.
More in Competition and admissions maths and the formula sheets.