On this page
Questions like "how many non-negative integer solutions does x + y + z = 10 have?" are a standard type in permutations and combinations practice, including for JEE Main. Listing solutions one by one is slow and error-prone. One picture, a row of stars split by bars, gives you the count in a single line.
How many non-negative integer solutions does x + y + z = 10 have?
The answer is 66. Here is how you get it.
Think of 10 as 10 identical stars. To split them among x, y and z you need 2 bars: stars before the first bar count towards x, stars between the bars towards y, and stars after the second bar towards z. The row ★★★|★★★★★|★★ means x = 3, y = 5, z = 2. The row |★★★★★★★|★★★ means x = 0, y = 7, z = 3, because nothing sits before the first bar.
Every row has 12 symbols: 10 stars and 2 bars. A solution is fixed as soon as you decide which 2 of the 12 places hold bars, so the count is C(12, 2) = (12 × 11) ÷ 2 = 66.
The general rule, set out as "Theorem two" in the Wikipedia article on stars and bars), is this: the number of non-negative integer solutions of x₁ + x₂ + … + xₖ = n is C(n + k − 1, k − 1). The same article works through x₁ + x₂ + x₃ + x₄ = 10 and gets C(13, 3) = 286.
Why does stars and bars work?
Every solution gives exactly one row of stars and bars, and every row gives back exactly one solution. So counting rows, which is just choosing bar positions, counts solutions.
Two details matter:
The stars are identical. Only how many stars land in each group matters, not which ones.
The variables are different. x = 3, y = 5 is not the same solution as x = 5, y = 3, and the bar picture keeps them apart because the groups sit in a fixed order.
If you are unsure whether a counting problem is about choosing or arranging, our guide to deciding between permutations and combinations has a quick test.
What changes when x, y and z must be positive?
Now each variable must be at least 1, so no two bars can touch and no bar can sit at either end. Put the 10 stars in a row. There are 9 gaps between them, and you place the 2 bars in 2 different gaps. The count is C(9, 2) = 36.
This matches "Theorem one" in the same Wikipedia article): the number of positive integer solutions of x₁ + … + xₖ = n is C(n − 1, k − 1).
You can also get there by substitution. Write x = a + 1, y = b + 1, z = c + 1 with a, b, c ≥ 0. Then a + b + c = 7, which has C(9, 2) = 36 non-negative solutions. The cp-algorithms page on stars and bars uses the same move for any lower bound: subtract each variable's minimum from n, then count non-negative solutions.
How do you count solutions when each variable is at most 5?
Upper limits need one more step: inclusion-exclusion, which the cp-algorithms page points to for this kind of constraint. Take x + y + z = 10 with 0 ≤ x, y, z ≤ 5.
Count everything with no cap: 66.
Count the bad cases where x ≥ 6. Write x = a + 6, so a + y + z = 4, which has C(6, 2) = 15 solutions. The same is true for y and for z, so there are 3 × 15 = 45 bad cases.
Check for overlaps. Two variables both at least 6 would add up to at least 12, which is more than 10, so there are none.
Subtract: 66 − 45 = 21.
To check by hand, fix x and count the (y, z) pairs that fit: 1 pair for x = 0, 2 for x = 1, up to 6 for x = 5, and 1 + 2 + 3 + 4 + 5 + 6 = 21. For more practice with this logic, try our worked example on counting numbers not divisible by 2, 3 or 5.
A 30-second checklist for exam questions
Are the things being shared out identical? If they are, stars and bars may fit. If not, you need a different count. Our box method for digit problems covers one common case.
Can a variable be 0? Yes: C(n + k − 1, k − 1). No: C(n − 1, k − 1).
Is there a lower bound? Subtract it from n first.
Is there an upper bound? Count everything, subtract the cases that break the cap, and add back any overlaps.
Test your formula on a small case you can list, such as x + y = 3 (4 solutions).
When you get the right answer by the wrong route, it helps to see each step laid out. The Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer. If the gap is the idea of a combination itself, the Fermi Concept Library gives each mathematics concept its own lesson.
