Stars and bars calculator
Count the number of integer solutions to x1 + … + xk = n for identical balls / boxes, with options for xi ≥ 0, xi ≥ 1, and xi ≥ ai (this is also combinations with repetition / multichoose).
How to use (3 steps)
- Enter n (total) and k (number of variables / boxes).
- Select the condition: xi ≥ 0, xi ≥ 1, or xi ≥ ai (optional: bounded).
- Copy a shareable URL to reproduce the same state.
Note: This page counts identical balls. If balls are distinct, the model is different.
Visual guide
For small inputs, this shows one example encoding with stars (*) and bars (|). It is an illustration, not “the only arrangement”.
Result
Steps (short)
Show the reasoning
Examples (solutions)
Show solutions for small n,k
Tip: Solutions listing is capped (performance). For large inputs, use the count only.
Formulas & common mistakes
- Nonnegative (xi≥0):
C(n+k−1, k−1) - This equals “combinations with repetition” (multichoose):
k multichoose n = C(n+k−1, n). - Positive (xi≥1):
C(n−1, k−1)(ifn<kthen0) - Lower bounds (xi≥ai): convert to
n−Σai, thenC((n−Σai)+k−1, k−1)
Common mistakes
- Mixing up “identical balls” vs “distinct balls”. This calculator is for identical balls (integer solutions).
- For xi≥1, remember
n<kgives0. - For lower bounds, ensure you subtract
Σai(not just a single a unless all ai are equal).
Related calculators
FAQ
What is the stars and bars method?
It counts the number of ways to distribute n identical items into k boxes, which is the number of solutions to x1+…+xk=n under conditions like xi≥0.
Why does the nonnegative case become C(n+k−1, k−1)?
Place n stars and k−1 bars in a row. Choosing bar positions uniquely determines a solution, giving C(n+k−1, k−1).
How does the formula change when xi≥1?
Let yi=xi−1. Then y1+…+yk=n−k with yi≥0, so the count is C(n−1, k−1) when n≥k, otherwise 0.
How do lower bounds xi≥ai work?
Let yi=xi−ai. Then y1+…+yk=n−Σai with yi≥0. If n≥Σai, the count is C((n−Σai)+k−1, k−1); otherwise 0.
What if the balls are distinguishable?
This calculator assumes identical balls. If balls are distinguishable, the model changes (often k^n or multinomial), so use a different calculator depending on the problem.