Stars and Bars Calculator
Use the stars and bars method to count combinations with repetition for x1 + ... + xk = n, including nonnegative, positive, lower-bound, and bounded cases.
Inputs
Results
This is the number of nonnegative integer solutions (x1,…,xk) to x1+…+xk=n.
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).
- Read the count, check the short steps or examples to confirm the model, then copy a shareable URL to reproduce the same state.
Note: This calculator 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”.
Visual guide (one example encoding, for small n,k)
This example corresponds to x = [3, 2, 2].
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). - For lower or upper bounds, check that the allowed values can still add up to n.
How to choose the right stars-and-bars setup
This calculator is for identical items distributed across boxes or variables. If order matters, or if the items are distinct, use a different counting model.
Why the bars matter
In the classic picture, each star is one item and each bar is a divider between boxes. Once you decide where the k−1 bars go among the n + k − 1 positions, you have fully described one solution.
How to choose the mode
- Use xi ≥ 0 when empty boxes are allowed.
- Use xi ≥ 1 when every box must receive at least one item.
- Use xi ≥ ai when each variable has a minimum.
- Use ai ≤ xi ≤ bi only when both lower and upper bounds are part of the problem.
Worked comparisons
If you place 7 identical balls into 3 boxes with empty boxes allowed, the count is C(9,2). If every box must get at least one ball, switch to the positive case and count C(6,2) instead. That contrast is usually the fastest way to catch whether a classroom problem is nonnegative or positive.
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.
When should I use positive instead of nonnegative?
Use the positive case when every variable or box must receive at least one item. Use the nonnegative case when zero is allowed. That single wording change is the most common source of wrong answers in stars-and-bars problems.
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.