The ● Balls / A Letters switch at the left of the control bar draws every item as the same red ball or the same letter A; the bars look the same in both modes. Learn more about the mode switch
The n stepper sets the number of identical items (3 to 5) and the k stepper the number of bins (2 to 4); each change clears the build and updates C(n+k−1,k−1) at the top right of the scene. Learn more about adjusting n and k
Step ▶ drops one bar into its cell, ◀ Back undoes one step, ▶ Play builds every composition and stops at the end, ↺ Reset clears the completed section, and Speed sets how fast the bars fly. Learn more about the transport controls
The top right of the scene shows the count C(n+k−1,k−1) and a status line such as x₁ = 0: 0 / 5. Learn more about getting started
The strip has n+k−1 numbered cells; bars land in cells, coloured bands mark the bins, and the brackets below read x1,x2,… as soon as the bars fix them, with a dashed mark for an empty bin. Learn more about the strip and bars
The COMPLETED section files each strip in the row of its first-bin count x1, from x1=0 up, with the count of finished compositions at its right. Learn more about grouping by first-bin count
The right panel adds one row per value of x1, with a counter such as 0 / 5 and the formula for that row; a ✓ marks each finished row. Learn more about the right panel
Press ▶ Play to build all C(n+k−1, k−1) weak compositions of n identical items into k bins (empty bins allowed), or Step ▶ to drop one bar at a time. A bin is the run of cells between two adjacent bars (or before the first / after the last); the count of items in bin i is xᵢ. Each outcome = a choice of k − 1 bar positions among n + k − 1 total cells.
Distribute n identical items into k distinct bins, with empty bins allowed. Count the solutions to x₁ + x₂ + … + xₖ = n in non-negative integers. Equivalently: choose k − 1 bar positions among n + k − 1 cells — the remaining cells hold the items.
Weak composition — a distribution of nidentical items into k distinct bins where bins may be empty. Equivalently, the number of non-negative integer solutions to x1+x2+⋯+xk=n. The count is (k−1n+k−1).
Stars and bars — the visual encoding of this problem. Draw n stars in a row and insert k−1 bars among them to split them into k groups. The count of arrangements is (k−1n+k−1) because there are n+k−1 total symbols and we choose k−1 positions for the bars.
Bin — the run of cells between two adjacent bars in the strip, or before the first bar, or after the last. The number of items in bin i is xi.
Strip — the row of n+k−1 cells where items (stars) and bars are placed. Each cell either holds one item or one bar.
Composition tuple (x1,x2,…,xk) — the encoded outcome: xi is the count of items in bin i, with x1+x2+⋯+xk=n and each xi≥0.
group — the family of weak compositions with the same first-bin count. The completed section groups results by x1; group sizes vary as (k−2n−j+k−2) for x1=j.
Getting Started
The tool opens with n=4 identical items and k=3 bins. The scene splits into three areas:
• A holding row at the top labeled *BARS TO PLACE (k − 1 = K)* showing the k−1 bars waiting to be inserted.
• A strip in the middle labeled *STRIP (n + k − 1 = N+K-1 cells)* — a row of n+k−1 cells, numbered 1 to n+k−1 above. The n items (identical, rendered as red balls or letter A) are pre-placed in the cells from the start. The animation moves the bars from the holding row into specific cell positions.
• A completed section below, where every finished composition is filed under the row matching its x1 value.
To run the visualization:
• Press ▶ Play to auto-build all (k−1n+k−1) weak compositions.
• Press Step ▶ to drop one bar at a time.
• Press ◀ to step backward.
• Adjust the Speed slider.
The header shows the formula C(n+k−1,k−1)=total alongside a live status line like *x1=j: k / size*.
(n, k) = (4, 3), idle, frozen
Four identical balls already seated in the strip; two bars waiting above. The items sit still — all the choice belongs to the dividers.
The frozen frame above is the opening position, and it reverses this section's usual casting: the items sit still — four identical red balls already in the strip — while the bars wait in the holding row above. The moving parts of a weak composition are the dividers, not the things being divided.
That inversion is the whole stars-and-bars insight in staging form: identical items carry no information, so all the choice lives in where the separators go. The bracket labels below the strip wait as question marks until the bars land.
The Strip and Bars
The strip is where the stars-and-bars encoding plays out:
• Numbered cells1 through n+k−1 across the top. The current cell where a bar lands highlights to mark its position.
• Pre-placed items (red balls or the letter A) sit in cells that aren't currently bar positions. Items are identical — same color, same size — because the scenario treats them as indistinguishable.
• Bins are highlighted with alternating color bands that cover only the cells inside each bin (not the bar cells). Bin 1 might be blue-tinted, bin 2 amber, bin 3 blue again, and so on.
• Bars arrive from the holding row above with a dotted guide line tracing the trajectory.
• Brackets below the strip mark each bin with a label xi=j. Brackets are progressive: each label shows ? until the relevant bar lands, then it reveals the actual value.
• Empty bins appear as dashed mini-rectangles in the bracket row, indicating that no cells lie between adjacent bars.
When all k−1 bars are placed, a flash ring pulses around the strip and the composition is filed in the completed grid below.
(4, 3) mid-build, frozen
The first bar landed at cell 1, sealing an empty first bin (x₁ = 0); the second rides its guide toward cell 3. The readout reads (0, 1, ?).
The frozen frame above catches the second composition mid-build: the first bar has landed at cell 1, pinning x1=0 — an empty first bin, marked by the dashed mini-rectangle in the bracket row — while the second bar rides its guide toward cell 3. The readout has hardened to (0,1,?).
Watch what each landing decides: a bar fixes the bin to its left, forever. That left-to-right hardening is why the tool can group results by x1 the moment the first bar lands — the stars-and-bars encoding reads off prefix by prefix.
Composition and Bar-Position Readouts
Under the strip, two readouts restate the current build in both encodings, joined by ⇔:
• composition: ( … ) — the bin counts (x1,x2,…,xk), zeros allowed.
• bar positions: { … } — the numbers of the cells that hold a bar.
Both start as question marks — (?,?,?) and {?,?} for the default n=4, k=3 — and fill in as bars land. In the first build, one Step ▶ puts a bar in cell 1: (0,?,?)⇔{1,?}, an empty first bin. The second bar lands in cell 2: (0,0,4)⇔{1,2} — two bars side by side leave the second bin empty too, and the last bin takes all four items. The brackets under the strip show the same values.
Below the readouts, a formula card spells out the count for the current n and k: Choose k − 1 = 2 bar positions out of n + k − 1 = 6 cells, followed by C(6,2)=6!/(2!⋅4!)=720/(2⋅24)=15. The card changes only with the n and k steppers; the readouts change with every bar.
The two-way arrow is the stars-and-bars argument in one line: each set of k−1 bar cells gives exactly one composition, and each composition gives back exactly one set of cells.
Adjusting n and k
DemoChanging n and k
Step 0 of 5
Two steppers in the control bar control the size:
• n sets the number of identical items. Range 3 to 5.
• k sets the number of distinct bins. Range 2 to 4.
Reducing n does not constrain k in this scenario, since even n=0 gives valid weak compositions (all xi=0). Changing either value resets the build, refreshes the formula in the header, and rebuilds the completed section into a new set of x1-rows.
Grouping by First-Bin Count
DemoRows by first-bin count
Step 0 of 4
The completed section organizes weak compositions by x1 — the count of items in the first bin. There are n+1 rows total (one for each value x1=0,1,2,…,n), and group sizes vary.
When x1=j, the remaining n−j items must be distributed among the remaining k−1 bins, also as a weak composition:
group size at x1=j=(k−2n−j+k−2)
For example with n=4,k=3:
• x1=0: distribute 4 items into 2 bins. (15)=5 compositions.
• x1=1: distribute 3 items into 2 bins. (14)=4 compositions.
• x1=2: distribute 2 items into 2 bins. (13)=3 compositions.
• x1=3: distribute 1 item into 2 bins. (12)=2 compositions.
• x1=4: distribute 0 items into 2 bins. (11)=1 composition.
Total: 5+4+3+2+1=15=(26). The decomposition is a visual proof of the hockey-stick identity∑j=0n(k−2n−j+k−2)=(k−1n+k−1).
C(6, 2) complete, frozen
Fifteen strips in rows of 5, 4, 3, 2, 1 — a perfect countdown, one option lost for each item the first bin claims.
The frozen frame above is that decomposition completed: fifteen strip cards in five rows of 5,4,3,2,1 — a perfect countdown, because each extra item claimed by the first bin removes exactly one option from the leftover problem.
The triangular row profile is this scenario's fingerprint, as distinctive as the combination tool's staircase or the distribution tool's flat rows. One glance at how a completed grid's rows shrink tells you which counting regime produced it.
Three Bars, Fifty-Six Ways
The tool's largest setting: n=5 items, k=4 bins, so three bars land among 5+4−1=8 cells — (38)=56 weak compositions.
Fifty-six cards spread across six x1-rows of sizes 21,15,10,6,3,1 — the triangular numbers, marching down as the first bin absorbs more items. Each row is itself a complete run of the smaller problem "distribute the remainder into three bins."
At this scale the strip encoding shows its efficiency: every one of the 56 outcomes is a distinct picture of eight cells, yet the whole enumeration is just *choose 3 cells from 8* — a selection the combination tool could count without drawing a single strip.
C(8, 3) complete, frozen
Three bars among eight cells: 56 compositions in triangular rows of 21, 15, 10, 6, 3, 1 — Pascal’s diagonal drawn as cards.
The row sizes deserve their name: 21,15,10,6,3,1 are consecutive triangular numbers, because each is itself a sum of the next row of counts — the hockey-stick identity stacked twice. Weak-composition counts are Pascal's triangle read along diagonals, and this grid is that diagonal drawn as cards.
Fifty-six is also where the identical-items assumption pays its dividend: the same five items distributed as distinct objects into four cells would give 45=1024 outcomes. Forgetting who's who collapses a thousand cases into fifty-six — see related concepts for that comparison.
Transport Controls
DemoStep, file, back
Step 0 of 5
The control bar offers four transport buttons plus a speed slider:
• ◀ (Step back) — walks the animation one step backward.
• Step ▶ (Step forward) — drops one bar into its cell. Stop after each step to read the partial composition; cells without bars yet show ? in their brackets.
• ▶ Play / ⏸ Pause — runs continuously until all (k−1n+k−1) weak compositions are built, then auto-pauses.
• ↺ Reset — clears the completed section and starts over.
The Speed slider controls how fast play advances. At slower speeds you can clearly see each bar travel from the holding row into its cell and watch the bin brackets update from ? to the actual count.
Mode Switch
DemoBalls and letters
Step 0 of 4
The Mode switch at the start of the control bar toggles how identical items are rendered:
• Balls mode (default) — items appear as red circles. All circles are identical because the items themselves are indistinguishable. Best for the classical stars-and-bars look.
• Letters mode — items appear as the letter A. Same identicality applies — every item shows the same letter in the same color. Best when reading compositions algebraically and emphasizing that the items are interchangeable.
The encoding is consistent across the strip, the mini cards in the completed grid, and the right-panel narration. Bars are unaffected — they always render as the same accent-colored vertical bars regardless of mode.
Right Panel and Progress
The right panel narrates the build as it unfolds, anchored by the header *Weak compositions (stars and bars)* with the full formula across multiple lines and a reminder that this counts non-negative integer solutions to x1+x2+⋯+xk=n.
A StepRow is added for each x₁-group as soon as a composition in that group starts or completes. Each StepRow shows:
• The first bin count as a label — *First bin: x1=j*.
• A progress counterk/(k−2n−j+k−2) tracking how many compositions in this group have completed.
• A short narration of the structure: *When the first bin holds j items (x1=j), the remaining n−j items are split among the other k−1 bins, giving (k−2n−j+k−2) outcomes.* Edge cases get tailored phrasing: x1=0 uses the first bin is empty; x1=n uses all items go to the first bin with the others empty.
When all groups complete, every StepRow shows done with a checkmark, and the counter reaches *total / total*.
What Is a Weak Composition
A weak composition of n into k parts is an ordered tuple (x1,x2,…,xk) of non-negative integers summing to n:
x1+x2+⋯+xk=n,xi≥0
The word weak distinguishes this from a strong composition, which requires every xi≥1. Weak compositions allow zero parts, so the first bin (or any bin) is permitted to be empty.
The count of weak compositions is:
(k−1n+k−1)=(nn+k−1)
Examples:
• Distributing 10 identical candies among 3 children (some children may get none): (212)=66 ways.
• Number of non-negative integer solutions to a+b+c+d=7: (310)=120.
• Choosing 5 scoops of ice cream from 6 flavors with repetition allowed (a flavor may be skipped): (510)=252 choices.
• Distributing n identical items into k labeled boxes with no capacity limit: the canonical setup.
For deeper coverage of weak compositions and their connections, see the weak composition section on the combinations theory page.
The Stars-and-Bars Argument
The classical proof maps weak compositions to a simple selection problem.
Encode each composition as a row of symbols. Write x1 stars, then a bar, then x2 stars, then a bar, and so on through xk stars. The total is n stars plus k−1 bars, giving n+k−1 symbols in a row.
Every weak composition is determined by where the bars sit. The bars partition the row into k groups; the ith group has xi stars. Different bar placements give different compositions, and every composition comes from a unique bar placement (including bars adjacent to each other, which encode xi=0).
Count the bar placements. We're choosing k−1 positions out of n+k−1 total to be bars (the rest are stars). The count is the binomial coefficient:
(k−1n+k−1)
This is the visual setup the tool implements. Each completed strip has n items in fixed (canonical) positions and k−1 bars in specific cells; the cells without bars hold the items, and the brackets below convert the bar positions back into the tuple (x1,…,xk).
The dual reading (nn+k−1) — choose the n star positions instead of the bars — gives the same count by complementary counting.
C(5, 1) complete, frozen
One bar, five cells, five cards: with two bins, "choose the bar positions" stops being a metaphor and becomes pointable.
The frozen frame above shows the argument at its barest: k=2 bins means a single bar, and the five completed cards are simply the five cells that one bar can occupy among n+1=5. "Choose the bar positions" stops being a metaphor — you can point at each choice.
With one bar the binomial collapses to (15)=5, and the composition tuple is just (j,n−j) — the bar's cell number decides everything. Every richer configuration is this picture with more bars to seat.
Related Concepts
Strong composition — the same setup but every bin must hold at least one item. Formula (k−1n−1). Smaller than the weak count because zero parts are forbidden.
Simple combination — the no-repetition unordered selection. (rn). Weak compositions can be seen as combinations with repetition allowed: choosing n items from k types with reuse equals weak compositions of n into k parts.
Combination with repetition — exactly the weak composition count (nn+k−1) under a different name and framing.
Distribution into cells — distributes ndistinct items (not identical) into k labeled cells. Formula kn, much larger than the weak composition count because items can be distinguished.
Multiset coefficient — the doubled-parenthesis notation ((nk)) for the weak composition count, emphasizing that the outcome is a size-n multiset over a k-element ground set.
Hockey-stick identity — the grouping by x₁ proves ∑j=0n(k−2n−j+k−2)=(k−1n+k−1).
Combinatorics calculator — to compute (k−1n+k−1) for any n and k, see the weak composition calculator.