DSAverse

Initializing Sorting Algorithms...

Sorting

Trees

Graphs

Preparing interactive visualizations...

Back to Combinatorics

Stars and Bars

Identical items into distinct bins. Line the items up as stars, split them with k − 1 bars, and every distribution becomes a row — so the count is a single binomial coefficient.

Step 1 of 14

Speed

Five identical cookies, three kids. Only how many each kid gets matters — the cookies cannot be told apart. Kid 1 gets 2, kid 2 gets 1, kid 3 gets 2: draw it as 5 stars split by 2 bars, **|*|**.

\binom{n + k - 1}{k - 1} = \binom{5 + 3 - 1}{3 - 1} = \binom{7}{2} = \mathbf{21}

\textcolor{#e879f9}{2} + \textcolor{#38bdf8}{1} + \textcolor{#fbbf24}{2} = 5\qquad x_1 + \dots + x_{3} = 5,\; x_i \ge 0

n (items)5k (bins)3

Row number (dictionary order of bar positions)13 of 21

Stars and Bars

Identical items into distinct bins. Line the items up as stars, split them with k − 1 bars, and every distribution becomes a row — so the count is a single binomial coefficient.

Step 1 of 14

Speed

Five identical cookies, three kids. Only how many each kid gets matters — the cookies cannot be told apart. Kid 1 gets 2, kid 2 gets 1, kid 3 gets 2: draw it as 5 stars split by 2 bars, **|*|**.

\binom{n + k - 1}{k - 1} = \binom{5 + 3 - 1}{3 - 1} = \binom{7}{2} = \mathbf{21}

\textcolor{#e879f9}{2} + \textcolor{#38bdf8}{1} + \textcolor{#fbbf24}{2} = 5\qquad x_1 + \dots + x_{3} = 5,\; x_i \ge 0

n (items)5k (bins)3

Row number (dictionary order of bar positions)13 of 21

DSAverse

Stars and Bars

See also

Stars and Bars

See also