What is the formula for strong compositions?

The number of strong compositions of n into exactly k positive parts is n minus 1 choose k minus 1. The derivation uses the n minus 1 gaps between adjacent items and chooses k minus 1 of them to place dividers. Each choice corresponds to a unique strong composition.

What is the difference between strong and weak composition?

A strong composition requires every part to be at least 1, so every bin is nonempty. A weak composition allows zero parts, so some bins may be empty. Strong compositions are counted by n minus 1 choose k minus 1; weak compositions by n plus k minus 1 choose k minus 1, which is always larger.

How many strong compositions does the number 5 have into 3 parts?

The number of strong compositions of 5 into exactly 3 positive parts is 4 choose 2 = 6. The compositions are (3,1,1), (1,3,1), (1,1,3), (2,2,1), (2,1,2), and (1,2,2).

When should I use the strong composition formula?

Whenever a problem distributes identical objects into distinguishable bins with the constraint that every bin receives at least one object. Common cases include splitting identical resources fairly so no recipient is left out, counting positive integer solutions to linear equations, and any scenario where empty groups are not allowed.

Strong Composition

How to use

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; bars and gaps look the same in both modes. Learn more about the mode switch
The n stepper sets the number of identical items (3 to 7) and the k stepper the number of bins (2 to 4, never more than $n$ ); each change clears the build and updates $C(n - 1, k - 1)$ at the top right of the scene. Learn more about adjusting n and k
Step ▶ drops one bar into its gap, ◀ 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 - 1, k - 1)$ and a status line such as x₁ = 1: 0 / 3. Learn more about getting started
In the items row, bars land only in the dashed drop-zones between items; coloured bands mark the bins and the brackets below read $x_1, x_2, \dots$ as soon as the bars fix them. Learn more about items and gaps
Under the strip, composition: ( … ) ⇔ chosen gaps: { … } shows the same build in both encodings, and the formula card writes out the full count. Learn more about the composition and gap readouts
The COMPLETED section files each strip in the row of its first-bin count $x_1$ , 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 $x_1$ , with a counter such as 0 / 3 and the formula for that row; a ✓ marks each finished row. Learn more about the right panel

● BallsA Letters

n =5?

k =3?

Speed

Strong compositions (positive parts)

C(n−1, k−1) = C(4, 2)
= 4! / (2! · 2!)
= 24 / (2 · 2)
= 6

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.

Bars land only between items — never at the ends — so "every bin gets at least one" is enforced by the board, not by arithmetic. Learn more about getting started · Adjusting n and k

Key Terms

Getting Started

Items and Gaps

Composition and Gap Readouts

Adjusting n and k

Grouping by First-Bin Count

Two Bins, One Divider

Twenty Ways: The Largest Run

When k = n: The Forced Composition

Transport Controls

Mode Switch

Right Panel and Progress

What Is a Strong Composition

The Gap-Choice Argument

Related Concepts

Key Terms

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

x_1 + x_2 + \dots + x_k = n

. The count is

\binom{n - 1}{k - 1}

.

Positive parts — the requirement

x_i \geq 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:

x_i

is the run length in bin

i

, with

x_1 + x_2 + \dots + x_k = n

and each

x_i \geq 1

.

group — the family of strong compositions with the same first-bin count. Group sizes vary as

\binom{n - j - 1}{k - 2}

for

x_1 = j

, with

j

ranging from

1

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

x_1

value.

To run the visualization:

• Press ▶ Play to auto-build all

\binom{n - 1}{k - 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) = \text{total}

alongside a live status line like *

x_1 = j

k

/ size*.

(n, k) = (5, 3), idle, frozen

Five items shoulder to shoulder with four dashed drop-zones between them — the only legal landing sites, and the reason no bin can end up empty.

The frozen frame above is the opening position, and the difference from its weak counterpart is written into the geometry: there are no cells for the bars. Five items sit shoulder to shoulder, and the only landing sites are the four dashed drop-zones between them — never before the first item, never after the last.

That single design choice does all the enforcement. A divider that can only land between two items can never leave a bin empty, so the constraint

x_i \geq 1

needs no checking — it is built into the board.

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

x_i = 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

x_i \geq 1

, as the gap-choice argument spells out.

(5, 3) mid-build, frozen

One bar seated in gap 1, sealing x₁ = 1; the second rides its guide toward gap 3. Bars can never share a gap, so bins never collapse to zero.

The frozen frame above catches the second composition mid-build: one bar already seated in gap 1 — sealing

x_1 = 1

— while the second rides its guide toward gap 3. The readout has hardened to

(1, 2, ?)

, and two drop-zones remain dashed and available.

Compare this to the weak tool's strip, where bars could land beside each other and collapse a bin to zero. Here adjacency is impossible: every gap holds at most one bar, and every bar has an item on each side. The rule is enforced by the furniture rather than by arithmetic.

Composition and Gap Readouts

Under the items row, two readouts restate the current build in both encodings, joined by ⇔:

• composition: ( … ) — the bin counts

(x_1, x_2, \dots, x_k)

.

• chosen gaps: { … } — the numbers of the gaps that hold a bar.

Both start as question marks —

(?, ?, ?)

and

\{?, ?\}

for the default

n = 5

k = 3

— and fill in as bars land. In the first build, one Step ▶ gives

(1, ?, ?) \Leftrightarrow \{1, ?\}

: the first bar in gap 1 seals

x_1 = 1

. The second gives

(1, 1, 3) \Leftrightarrow \{1, 2\}

, and the last bin is known only now, because it runs from the last bar to the end of the row. The same values appear in the brackets under the items.

Below the readouts, a formula card spells out the count for the current

n

and

k

: Choose k − 1 = 2 gaps out of n − 1 = 4 gaps between items, followed by

C(4, 2) = 4!/(2! \cdot 2!) = 24/(2 \cdot 2) = 6

. The card changes only with the n and k steppers; the readouts change with every bar.

The two-way arrow is the gap-choice argument in one line: each set of

k - 1

gaps gives exactly one composition, and each composition gives back exactly one set of gaps.

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

7

.

• k sets the number of bins. Range

2

4

, with the additional constraint

k \leq n

(you can't have more nonempty bins than items).

Common combinations:

•

n = 3, k = 2

\binom{2}{1} = 2

compositions:

(2, 1)

and

(1, 2)

.

•

n = 4, k = 2

\binom{3}{1} = 3

compositions — one bar among the gaps.

•

n = 5, k = 3

\binom{4}{2} = 6

compositions — the default configuration.

•

n = 6, k = 3

\binom{5}{2} = 10

compositions.

•

n = 7, k = 4

\binom{6}{3} = 20

compositions — the largest run on this page.

•

n = k

: exactly

1

composition — every gap takes a bar.

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

x_1

-rows.

Note the symmetry with binomial coefficients:

\binom{n - 1}{k - 1} = \binom{n - 1}{n - k}

. For example

\binom{6}{2} = \binom{6}{4} = 15

— the same count interpreted as choosing gap positions or choosing non-divider positions.

Grouping by First-Bin Count

DemoRows by first-bin count

Step 0 of 5

The completed section organizes strong compositions by

x_1

— the count of items in the first bin. There are

n - k + 1

rows total (since

x_1

ranges from

1

n - k + 1

, with the cap ensuring the remaining

k - 1

bins can each hold at least one item).

When

x_1 = j

, the remaining

n - j

items must form a strong composition of size

k - 1

\text{group size at } x_1 = j = \binom{n - j - 1}{k - 2}

For example with

n = 5, k = 3

:

•

x_1 = 1

: split 4 items into 2 nonempty bins.

\binom{3}{1} = 3

compositions.

•

x_1 = 2

: split 3 items into 2 nonempty bins.

\binom{2}{1} = 2

compositions.

•

x_1 = 3

: split 2 items into 2 nonempty bins.

\binom{1}{1} = 1

composition.

Total:

3 + 2 + 1 = 6 = \binom{4}{2}

.

The decomposition gives a visual proof of

\sum_{j=1}^{n-k+1} \binom{n - j - 1}{k - 2} = \binom{n - 1}{k - 1}

, a shifted variant of the hockey-stick identity.

C(4, 2) complete, frozen

Six strips in rows of 3, 2, 1 — a countdown that starts at x₁ = 1, because every other bin is owed an item of its own.

The frozen frame above is that example completed: six strips in rows of

3

2

1

. The countdown is shorter than the weak tool's — it starts at

x_1 = 1

rather than

0

, and stops at

x_1 = 3

rather than

5

, because the other bins each demand an item of their own.

Those missing rows are the whole difference between the two scenarios. Weak compositions of 5 into 3 number

\binom{7}{2} = 21

; strong ones number

6

. The gap between them is the price of the phrase at least one.

Two Bins, One Divider

Set

k = 2

and the whole scenario collapses to a single question: *where does the one bar go?* With

n = 5

items there are

4

gaps, so

\binom{4}{1} = 4

compositions —

(1,4), (2,3), (3,2), (4,1)

.

Every composition is named by its bar's gap number, and the tuple is always

(j, n - j)

for the gap

j

chosen. Nothing is hidden: the count of compositions equals the count of gaps.

Note that

(0, 5)

and

(5, 0)

are missing, and their absence is the point — those would need a bar outside the row, which the drop-zones do not offer.

C(4, 1) complete, frozen

One bar, four gaps, four compositions: each card is named by the gap its divider occupies, and the tuple is always (j, n − j).

This is the cleanest place to feel why the strong count uses

n - 1

rather than

n + 1

. The weak version of the same question allows the bar to sit at either end as well, giving

\binom{6}{1} = 6

— the same four splits plus the two lopsided ones with an empty bin.

Two bins also connects to a familiar object: splitting a row of

n

items into a nonempty prefix and a nonempty suffix is exactly choosing a cut point, and there are

n - 1

of those. Many "in how many ways can a sequence be broken" questions reduce to this count.

Twenty Ways: The Largest Run

The tool's largest setting:

n = 7

items,

k = 4

bins, so three bars choose among six gaps —

\binom{6}{3} = 20

strong compositions.

The four

x_1

-rows hold

10, 6, 3, 1

cards. Each is itself a complete smaller run: after the first bin takes

j

items, the remainder is a strong composition of

7 - j

into

3

parts, and those counts

\binom{5}{2}, \binom{4}{2}, \binom{3}{2}, \binom{2}{2}

are the triangular numbers walking down.

Twenty is also the middle of Pascal's sixth row —

\binom{6}{3}

is the largest binomial coefficient available at that level, which makes this the most crowded strip the tool can draw.

C(6, 3) complete, frozen

Twenty compositions in rows of 10, 6, 3, 1 — the centre of Pascal’s sixth row, the most crowded strip the tool can draw.

The central-binomial position is not a coincidence of the caps: for fixed

n

, the strong-composition count

\binom{n-1}{k-1}

peaks when

k - 1

is half of

n - 1

— bins that are neither too few nor too many. Splitting seven items into four bins is the most "uncertain" question this tool can ask.

Summing across all

k

for

n = 7

would give

2^6 = 64

compositions in total, of which these twenty are the four-bin share — the largest single slice, as related concepts notes.

When k = n: The Forced Composition

Push

k

up to

n

and the freedom vanishes: with as many bins as items and every bin demanding at least one, each bin must hold exactly one. The count bottoms out at

\binom{n - 1}{n - 1} = 1

and the single composition is

(1, 1, \dots, 1)

.

The picture makes the reasoning unnecessary: there are

n - 1

gaps and

n - 1

bars, so every gap takes a bar. Nothing is left to choose — the completed section holds one card, with every item fenced off alone.

This is also the boundary the

k \leq n

constraint protects. Asking for

k > n

nonempty bins is impossible, and the formula agrees:

\binom{n-1}{k-1} = 0

when

k - 1 > n - 1

k = n complete, frozen

Every gap takes a bar and every bin holds exactly one item: a single card, the forced composition (1, 1, 1, 1).

Both extremes of the stepper now have names: at k = 2 one bar roams freely among many gaps, and here every gap is occupied. Between them the count rises and falls along a row of Pascal's triangle, peaking near the middle as the largest run shows.

The zero case beyond the boundary is worth stating because word problems produce it constantly: *"distribute 4 identical prizes among 6 people, everyone getting at least one"* has no solutions at all, and the binomial coefficient reports that honestly rather than erroring.

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 chosen gap. Stop after each step to read the partial composition; un-marked bins show

?

in their brackets.

• ▶ Play / ⏸ Pause — runs continuously until all

\binom{n - 1}{k - 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

DemoBalls and letters

Step 0 of 4

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

x_1 + x_2 + \dots + x_k = n

via choosing

k - 1

n - 1

gaps.

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:

x_1 = j

*.

• A progress counter

k / \binom{n - j - 1}{k - 2}

tracking how many compositions in this group have completed.

• A short narration of the structure: *When the first bin holds

j

items (

x_1 = j

), the remaining

n - j

items are split among the other

k - 1

bins (each

\geq 1

), giving

\binom{n - j - 1}{k - 2}

outcomes.* Edge cases get tailored phrasing:

x_1 = 1

describes the minimum first-bin case;

x_1 = 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

(x_1, x_2, \dots, x_k)

of positive integers summing to

n

x_1 + x_2 + \dots + x_k = n, \quad x_i \geq 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:

\binom{n - 1}{k - 1}

The total number of compositions of

n

(with any number of positive parts) is

2^{n-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:

\binom{9}{2} = 36

.

• Number of positive integer solutions to

a + b + c + d = 10

\binom{9}{3} = 84

.

• Compositions of

5

into exactly

3

parts:

\binom{4}{2} = 6

, namely

(3,1,1), (1,3,1), (1,1,3), (2,2,1), (2,1,2), (1,2,2)

.

• Total compositions of

4

2^3 = 8

across all values of

k

.

On this page the idea runs live: from the opening row of items, bars drop into the gaps between them, results group into x₁-rows, and the n and k steppers run the count from the single-divider case through twenty ways to the forced composition at

k = n

.

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

i

th run is bin

i

, and its length is

x_i

. Every

x_i \geq 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:

\binom{n - 1}{k - 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

(x_1, \dots, x_k)

.

Connection to weak compositions. Set

y_i = x_i - 1 \geq 0

. Then

y_1 + \dots + y_k = n - k

is a weak composition, counted by

\binom{n - k + k - 1}{k - 1} = \binom{n - 1}{k - 1}

. Same formula, derived two ways.