Stars and Bars Count

Count the number of ways to distribute n identical items into k bins using stars and bars.

combinatorics math combinations stars-and-bars

In combinatorics, the stars and bars method counts the number of ways to distribute n identical items into k distinct bins, where bins may be empty. The formula is C(n + k - 1, k - 1) = C(n + k - 1, n).

Write a function `stars_and_bars_count(n, k)` that takes two non-negative integers n and k (k >= 1) and returns the number of distributions as an integer. Note that 0! = 1, so if n = 0 and k = 1, the answer is 1 (one way: no items in the single bin).

Implement the function using factorial-based computation or math.comb if you wish, but do not rely on external libraries beyond Python's standard library.

Constraints

0 <= n <= 1000, 1 <= k <= 1000. The result may be large but will fit within Python's int (the return value is an integer). Your solution should run in O(n + k) time or better.

Example

>>> stars_and_bars_count(5, 3)
21
>>> stars_and_bars_count(0, 5)
1
>>> stars_and_bars_count(10, 1)
1

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

The number of ways is the binomial coefficient C(n+k-1, k-1).

You can compute C(a, b) using math.comb(a, b).

If k == 1, the answer is always 1 regardless of n.

Remember that n=0 gives exactly one way: all bins empty.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.