Press ▶ Play to build all C(n−1, k−1) strong compositions of n identical items into k bins, where every bin must hold at least one item. A bin is a run of consecutive items between two chosen gaps (or before the first / after the last); the count of items in bin i is xᵢ ≥ 1. Each outcome = a choice of k − 1 gap positions out of the n − 1 gaps between adjacent items.
Distribute n identical items into k distinct bins, with every bin holding at least one item. Count the solutions to x₁ + x₂ + … + xₖ = n in positive integers (xᵢ ≥ 1). Equivalently: choose k − 1 of the n − 1 gaps between adjacent items to place dividers — no two at the same gap, none at the ends.
Strong composition — a distribution of n identical items into k distinct bins where every bin must hold at least one item. Equivalently, the number of positive integer solutions to x1+x2+⋯+xk=n. The count is (k−1n−1).
Positive parts — the requirement xi≥1 for every i, which distinguishes strong from weak compositions. Empty bins are not allowed.
Gap — the space between two adjacent items in the row. With n items, there are exactly n−1 gaps available, and each gap can hold at most one divider.
Divider / bar — the k−1 vertical bars placed in chosen gaps that split the n items into k runs. Two dividers cannot share a gap, and no divider sits at the start or end (those would create empty bins).
Composition tuple $(x_1, x_2, \dots, x_k)$ — the encoded outcome: xi is the run length in bin i, with x1+x2+⋯+xk=n and each xi≥1.
$x_1$-group — the family of strong compositions with the same first-bin count. Group sizes vary as (k−2n−j−1) for x1=j, with j ranging from 1 to n−k+1.
Getting Started
The tool opens with n=5 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 dividers waiting to be inserted.
• An items row in the middle labeled *ITEMS (n = N) · GAPS (n − 1 = N-1)* — a row of n identical items with the n−1 gaps between them numbered 1 through n−1.
• 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−1) strong 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−1,k−1)=total alongside a live status line like *x1=j: k / size*.
Items and Gaps
The strip is where the gap-selection encoding plays out. Five things to watch:
• n items (identical red balls or letter A) sit fixed in their cells from the start. The items themselves never move — only the dividers do.
• n − 1 gap drop-zones sit between adjacent items as dashed mini-rectangles, numbered above. These are the only places a divider can land.
• Bin bands highlight runs of consecutive items in alternating colors (blue and amber). Items in bin 1 get one tint, bin 2 the other, bin 3 the first again, and so on.
• Bars arrive from the holding row above with a dotted guide line in the bar's color tracing the trajectory. Each bar lands in a specific gap; the gap's drop-zone outline disappears once filled.
• Brackets below the items mark each bin with a label xi=j. Brackets are progressive: each label shows ? until enough bars land to determine the run length.
When all k−1 bars are placed, a flash ring pulses around the strip and the composition is filed in the completed grid below.
Notice what's impossible here: a bar cannot sit at position 0 (before item 1) or position n (after item n), and two bars cannot share a gap. Both restrictions are exactly what enforces xi≥1.
Adjusting n and k
Two steppers in the control bar control the size:
• n sets the number of identical items. Range 3 to 7.
• k sets the number of bins. Range 2 to 4, with the additional constraint k≤n (you can't have more nonempty bins than items).
Common combinations:
• n=3,k=2: (12)=2 compositions: (2,1) and (1,2).
• n=4,k=2: (13)=3 compositions.
• n=5,k=3: (24)=6 compositions.
• n=6,k=3: (25)=10 compositions.
• n=7,k=4: (36)=20 compositions.
Reducing n below the current k clamps k down automatically. Changing either value resets the build, refreshes the formula in the header, and rebuilds the completed section into the new set of x1-rows.
Note the symmetry with binomial coefficients: (k−1n−1)=(n−kn−1). For example (26)=(46)=15 — the same count interpreted as choosing gap positions or choosing non-divider positions.
Grouping by First-Bin Count
The completed section organizes strong compositions by x1 — the count of items in the first bin. There are n−k+1 rows total (since x1 ranges from 1 to n−k+1, with the cap ensuring the remaining k−1 bins can each hold at least one item).
When x1=j, the remaining n−j items must form a strong composition of size k−1:
The decomposition gives a visual proof of ∑j=1n−k+1(k−2n−j−1)=(k−1n−1), a shifted variant of the hockey-stick identity.
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 chosen gap. Stop after each step to read the partial composition; un-marked bins show ? in their brackets.
• ▶ Play / ⏸ Pause — runs continuously until all (k−1n−1) strong 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 a specific gap drop-zone, and watch the bin brackets update from ? to the actual run length.
Mode Switch
The Mode switch at the start of the control bar toggles how the 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 visual of dividing a row of dots.
• Letters mode — items appear as the letter A. Same identicality applies — every item shows the same letter. Best when reading compositions algebraically and emphasizing that the items are interchangeable.
The encoding is consistent across the items row, the mini cards in the completed grid, and the right-panel narration. Bars and gap drop-zones are unaffected — they always render as accent-colored bars and dashed outlines regardless of mode.
Right Panel and Progress
The right panel narrates the build as it unfolds, anchored by the header *Strong compositions (positive parts)* with the formula across multiple lines and a reminder that this counts positive integer solutions to x1+x2+⋯+xk=n via choosing k−1 of n−1 gaps.
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−1) 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 (each ≥1), giving (k−2n−j−1) outcomes.* Edge cases get tailored phrasing: x1=1 describes the minimum first-bin case; x1=n−k+1 describes the maximum where the other bins each hold exactly 1.
When all groups complete, every StepRow shows *done* with a checkmark, and the counter reaches *total / total*.
What Is a Strong Composition
A strong composition of n into k parts is an ordered tuple (x1,x2,…,xk) of positive integers summing to n:
x1+x2+⋯+xk=n,xi≥1
The word *strong* (sometimes simply *composition*) distinguishes this from a weak composition, which allows zero parts. Every strong composition is also a weak composition with no zeros.
The count of strong compositions is:
(k−1n−1)
The total number of compositions of n (with any number of positive parts) is 2n−1, since each of the n−1 gaps independently has or does not have a bar.
Examples:
• Ways to split 10 identical pencils among 3 kids so each gets at least one: (29)=36.
• Number of positive integer solutions to a+b+c+d=10: (39)=84.
• Compositions of 5 into exactly 3 parts: (24)=6, namely (3,1,1),(1,3,1),(1,1,3),(2,2,1),(2,1,2),(1,2,2).
• Total compositions of 4: 23=8 across all values of k.
For deeper coverage of strong compositions, see the strong composition section on the combinations theory page.
The Gap-Choice Argument
The classical proof maps strong compositions to a simple gap-selection problem.
Arrange the $n$ items in a row. Between each pair of adjacent items there is a gap, giving n−1 gaps total. The gaps are the only candidate sites for dividers — putting a divider before the first item or after the last would create an empty bin, which strong compositions don't allow.
A strong composition is determined by which $k - 1$ gaps hold dividers. Choose any k−1 of the n−1 gaps to receive a bar. The bars partition the row into k runs of consecutive items; the ith run is bin i, and its length is xi. Every xi≥1 automatically because there's at least one item between any two adjacent bars (and at the ends).
Count the selections. Choosing k−1 items from a set of n−1 is a binomial coefficient:
(k−1n−1)
This is exactly the visual the tool implements. The n items sit fixed; the n−1 gaps appear as dashed drop-zones; the user (or the auto-play loop) drops k−1 bars into chosen gaps; the bin brackets convert the chosen-gap set back into the tuple (x1,…,xk).
Connection to weak compositions. Set yi=xi−1≥0. Then y1+⋯+yk=n−k is a weak composition, counted by (k−1n−k+k−1)=(k−1n−1). Same formula, derived two ways.
Related Concepts
Weak composition — same setup but empty bins allowed. Formula (k−1n+k−1). Always at least as large as the strong count because zero parts are permitted.
Simple combination — the no-repetition unordered selection. (rn). The strong-composition formula is itself a binomial coefficient, (k−1n−1) — choosing gap positions out of available gaps.
Distribution into cells — distributes ndistinct items (not identical) into k labeled cells with no capacity rule. Formula kn.
Partition into groups — distributes n distinct items into k labeled boxes of fixed sizes. Multinomial coefficient n!/(n1!⋯nk!).
Total number of compositions — across all values of k from 1 to n, summing ∑k=1n(k−1n−1)=2n−1. Each of the n−1 gaps is independently a bar or not.
Bijection $x_i \mapsto x_i - 1$ — converts strong compositions of n into k parts into weak compositions of n−k into k parts. Both counted by (k−1n−1).
Hockey-stick identity — grouping by x1 proves ∑j=1n−k+1(k−2n−j−1)=(k−1n−1).
Combinatorics calculator — to compute (k−1n−1) for any n and k, see the strong composition calculator.