Optional method

Stars and bars

Count ways to split identical objects between labelled groups by turning the split into a row of objects and separators.

When it's useful

  • The question asks for non-negative or positive integer solutions to a fixed-total equation.

  • The objects are identical, the groups are labelled and order inside a group does not matter.

  • There are no individual upper bounds, or a simple lower bound can be removed first.

Check these conditions first

  1. 1

    For the standard form, every variable must be an integer with xi≥0x_i\geq 0.

  2. 2

    A condition such as xi≥1x_i\geq 1 must be removed by giving each group its compulsory first object before counting what remains.

  3. 3

    Do not use the basic formula when the objects are distinct, the groups are unlabelled or a variable has an upper bound.

The result

For integers n≥0n\geq0 and k≥1k\geq1, the number of non-negative integer solutions to x1+x2+⋯+xk=nx_1+x_2+\cdots+x_k=n is (n+k−1k−1)\binom{n+k-1}{k-1}. If every variable is positive and n≥kn\geq k, the count is (n−1k−1)\binom{n-1}{k-1}.

Why it works

Represent the nn identical objects by nn stars in one row.

Insert k−1k-1 bars. The objects before the first bar go to group 11, those between the first two bars go to group 22, and so on. Adjacent bars correctly represent an empty group.

The row contains n+k−1n+k-1 positions in total, and choosing the k−1k-1 bar positions determines exactly one allocation.

Therefore the count is (n+k−1k−1)\binom{n+k-1}{k-1}. For positive variables, first place one object in every group, leaving n−kn-k objects to allocate without restriction.

Worked example

Ten identical counters are placed into four labelled boxes, with at least one counter in each box. How many allocations are possible?

Try it first, then show the solution
  1. 1

    Let the box counts be x1,x2,x3,x4x_1,x_2,x_3,x_4, so x1+x2+x3+x4=10x_1+x_2+x_3+x_4=10 with every xi≥1x_i\geq1.

  2. 2

    Put one compulsory counter in each box. Write yi=xi−1y_i=x_i-1, so every yi≥0y_i\geq0.

  3. 3

    The remaining equation is y1+y2+y3+y4=6y_1+y_2+y_3+y_4=6.

  4. 4

    Represent the six remaining counters by six stars and the four boxes by three separating bars.

  5. 5

    Choose the three bar positions from the nine total positions: (93)=84\binom{9}{3}=84.

Answer

There are 8484 allocations.

Check yourself

Try this without looking back at the example.

How many non-negative integer solutions are there to a+b+c=7a+b+c=7?

Answer options
  • Probability & combinatorics · PremiumCount arrangements without duplication
  • Probability & combinatorics · PremiumUse complements and constraints
All free methods

Your next step

Use it on real TMUA questions

Free, no account needed

Take the timed diagnostic

20 Forge-original questions under exam timing, calibrated to the 2023 paper's difficulty profile. You get a score and a topic-by-topic breakdown at the end.

Start the free diagnostic

Free account

Save your progress

Create a free account for 41 free lessons and 4 methods in Learn, with progress kept on this device, and free sittings of released past papers.

Create a free account

Premium

Practise at the harder level

561 Forge originals calibrated for the harder computer-based papers sat since 2024, with worked solutions, unlimited mocks, all 104 lessons and 18 methods.

£49 for 12 months or £20 for 30 days. One payment, no automatic renewal.

See premium