Skip to content
Omnikalc

Stars and bars calculator: count the ways to share identical items between people or boxes, with a minimum for each

Enter the number of identical items, the number of bins and a minimum per bin to count the distributions with the stars and bars method.

Updated on
Your inputs

Value out of range

Value out of range

Value out of range

Results

Ways to distribute with the minimum in each bin

35

Ways with empty bins allowed
455
Ways with at least 1 item in each bin
165
Free items left after the minimum
4
Share of the unrestricted ways that meet the minimum
7.7 %

The stars and bars method counts the ways to share identical items among different bins. The stars and bars calculator gives the number of distributions with a minimum in each bin, with empty bins allowed, and with at least one item in each bin.

How the calculation works

  • Enter the number of identical items to share, such as candies, coins or balls.
  • Enter the number of bins, such as children, boxes or days, and the minimum that each bin must receive (0 if bins may stay empty).
  • The calculator removes the minimum from each bin and counts the ways to share the free items with the formula C(free + bins − 1, bins − 1).
  • It also shows the counts with empty bins allowed and with at least one item in each bin.

Example

You share 12 identical candies between 4 children, and each child must get at least 2. After the minimum, 12 − 4 × 2 = 4 candies are free, and they can be shared in C(4 + 3, 3) = 35 ways. If empty hands were allowed, there would be C(15, 3) = 455 ways, and with at least one candy each, C(11, 3) = 165 ways. The condition of 2 each keeps 7.7 % of the unrestricted ways.

Why it matters

The calculator helps students of discrete mathematics and probability, teachers, programmers and puzzle lovers to count the solutions of an equation in integers or the ways to share goods. It shows the effect of a minimum on the number of possibilities, which is hard to see in the formula alone.

Good to know

The method needs identical items and distinguishable bins. If the items are different from each other, or the bins identical, the count is another one. The calculator limits n to 60 and the number of bins to 12 so the numbers stay exact, and for upper limits on a bin the inclusion–exclusion method is needed.

The combinations calculator counts the choices C(n, k) used in the formula, the permutations calculator counts ordered arrangements, the derangements calculator counts the arrangements with no fixed place, and the hypergeometric distribution calculator finds probabilities when drawing without replacement.

Frequently asked questions

What is the stars and bars method?

Stars and bars is a counting trick for sharing identical items among bins. Draw the items as stars and the separations between bins as bars. To share n items among k bins you need k − 1 bars, and a distribution is a choice of the places of the bars among the n + k − 1 symbols, which gives C(n + k − 1, k − 1) ways.

How do I handle a minimum in each bin?

Give the minimum to each bin first, and share the remaining items freely. With n items, k bins and a minimum m, the free items are n − k × m, and the number of ways is C(n − k × m + k − 1, k − 1). If n − k × m is negative, there is no valid distribution. A minimum of 1 gives C(n − 1, k − 1).

Are the bins different from each other?

Yes, the method counts distributions where the bins are distinguishable, as when each bin is a different person or a different day. Giving 3 candies to Ann and 1 to Ben is different from giving 1 to Ann and 3 to Ben. If the bins are identical, the problem is about partitions of a number, which is a different count.

Where is the method used?

It is used to count the solutions in non-negative integers of an equation x1 + x2 + … + xk = n, to count the multisets of a given size, to share resources and to solve probability problems with a number of identical balls in boxes. It appears in courses of discrete mathematics and of combinatorics, and in the analysis of algorithms.

Was this calculator helpful?

Thanks for your feedback!

Results are estimates provided for information purposes. They do not replace professional advice.