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 n identical 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 $(x_1, x_2, \dots, x_k)$ — the encoded outcome: xi is the count of items in bin i, with x1+x2+⋯+xk=n and each xi≥0.
$x_1$-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*.
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.
Adjusting n and k
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.
Common combinations:
• n=3,k=2: (14)=4 compositions.
• n=3,k=3: (25)=10 compositions.
• n=4,k=3: (26)=15 compositions.
• n=4,k=4: (37)=35 compositions.
• n=5,k=3: (27)=21 compositions.
• n=5,k=4: (38)=56 compositions.
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
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).
Transport Controls
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
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 x1-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.
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.
Partition into groups — distributes n distinct items into k labeled boxes of fixed sizes. Multinomial coefficient n!/(n1!⋯nk!).
Multiset coefficient((nk)) — equivalent notation 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 x1 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.