Skip to content

Stars and Bars

Description

Let n,k∈Nn,k\in\mathbb{N}. Stars and bars is a counting method for the number of ways to distribute kk identical objects among nn distinct boxes, often by representing objects as stars and dividers as bars.

Interpretation

Stars and bars turns a problem of distributing identical objects among boxes into an arrangement problem. It is useful when objects are identical and only the counts in each box matter.

A row of six stars split by two bars into groups of 2, 1 and 3, representing one way to put six identical items into three boxes.

The six stars and two bars in the figure represent (x1,x2,x3)=(2,1,3)(x_1,x_2,x_3)=(2,1,3). Every arrangement of six stars and two bars corresponds to one nonnegative integer solution of x1+x2+x3=6x_1+x_2+x_3=6. Choosing the two bar positions among eight positions gives (82)=28\binom{8}{2}=28 distributions. In the general notation below, kk objects and nn boxes require n−1n-1 bars.

Key Results

  • Stars and bars counts nonnegative integer solutions to x1+⋯+xn=kx_1+\cdots+x_n=k.
  • The number of such solutions is (k+n−1n−1)\binom{k+n-1}{n-1}.
  • Positive integer solutions can be counted by first giving one object to each box.

Examples

  • The number of ways to distribute ten identical candies among four children is a stars-and-bars count.
  • The number of nonnegative solutions to x1+x2+x3=8x_1+x_2+x_3=8 is counted by stars and bars.
  • Allocating identical spare parts among labelled warehouses can use stars and bars.

Prerequisites

Sources

Keywords: combinations with repetition, multiset coefficient, Bose-Einstein counting Symbols: element of, natural numbers

Last updated: 20 October 2026 03:02