// COMBINATORICS · INTERMEDIATE

Stars and Bars

Count the ways to distribute n identical objects into k distinct bins — a fundamental combinatorics technique.

Visualize Distributions Play Distribute It!
Intermediate·20 min·Combinatorics
Reviewed by CodeTikki Academic Team

Prerequisites: Permutations & Combinations · Binomial coefficients

// DISTRIBUTION VISUALIZER

Stars, bars, and bins

Adjust the number of stars and bins to see distributions. The bars separate bins, and stars fill them.

Bin 1
Bin 2
Bin 3

Non-negative count

C(7+3-1, 3-1) = 36

Positive count

C(7-1, 3-1) = 15

// KEY FORMULAS

Stars and bars formulas

Non-negative

C(n + k - 1, k - 1)

Distribute n stars into k bins, bins can be empty

Positive

C(n - 1, k - 1)

Each bin gets at least 1 star (n ≥ k)

Lower bound (xi ≥ a)

C(n - k·a + k - 1, k - 1)

Substitute yi = xi - a, then non-negative

Upper bound (xi ≤ b)

Inclusion-exclusion

Subtract overflows: yi = xi - (b+1)

// ALGORITHM

Counting with upper bounds (inclusion-exclusion)

When variables have upper bounds, use inclusion-exclusion to subtract cases that violate the constraint.

// PSEUDOCODE · Count with Upper Bounds (Inclusion-Exclusion)
Stars and bars with xi ≤ bounds[i]
n = 10, k = 3, bounds = [4, 4, 4]
1function countWithUpperBounds(n, k, bounds):
2 total = C(n + k - 1, k - 1) // unconstrained
3 for subset S of {1..k}:
4 overflow = sum(bounds[i] + 1 for i in S)
5 if overflow > n: continue
6 ways = C(n - overflow + k - 1, k - 1)
7 if |S| is odd: total -= ways
8 else: total += ways
9 return total

Press PLAY to step through the algorithm line by line.

0 / 8

// INTERACTIVE GAME

Distribute It!

Given n stars and k bins, count the number of distributions. Choose between non-negative and positive modes!

Distribute It!

Count the number of ways to distribute stars into bins

You'll be given n stars and k bins. Count the number of distributions!

// FLOWCHART

Solving distribution problems

// FLOWCHART · Solving Distribution Problems
Stars and bars with constraints
YesNoYesNoStartIdentify objects& binsAnyconstraints?Transform tostandard formApply formuladirectlyUpper bounds?Use inclusion-exclusionApply C(n+k-1,k-1)or C(n-1,k-1)Verify smallcasesDone

Press PLAY to trace the algorithm through the flowchart.

0 / 10

// TUTORIAL QUIZZES

Test your mastery

From basic distributions to inclusion-exclusion with upper bounds.

// PRACTICE & ASSESS

Test your understanding

Now that you've learned the concept, put it into practice. Solve coding problems and take quizzes to reinforce what you've learned.

💻

Coding Problems

Count ways to distribute n candies among k childrenL4Integer solutions to x₁+x₂+x₃ = n with boundsL6Count multisets of size k from n typesL5Solve x₁+x₂+...+xₖ = n with xi ≤ b (inclusion-exclusion)L7Distribute n items with lower bounds on each binL6

// REFERENCES

Sources & further reading

  1. [1]
    Concrete MathematicsRonald L. Graham, Donald E. Knuth, Oren Patashnik — stars and bars method
  2. [2]
    A Walk Through CombinatoricsMiklós Bóna — distribution counting techniques
  3. [3]
    Introduction to CombinatoricsDavid R. Mazur — combinatorial methods
  4. [4]
    Principles and Techniques in CombinatoricsChen Chuan-Chong & Koh Khee-Meng — counting distributions

// READY?

Reason under uncertainty with probability

Next up: Probability Basics — sample spaces, conditional probability, Bayes' theorem, and expected value.

Probability Basics Browse Tutorials