Distributing Identical Objects (≥ 1 each) Explained with Worked Examples

The number of solutions of in positive integers is . With non-negative integers it is .

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Distributing identical objects (≥ 1 each) means

Picture identical objects in a row, with gaps between them. To split them into non-empty groups, choose of the gaps to put dividers in: that is ways, a counting argument based on binomial coefficients. This is the "stars and bars" method.

If groups may be empty, add 1 to each variable: satisfies with each , giving . Other lower bounds are handled by shifting in the same way. For ordered choices see the product rule, and for circular seating see circular arrangements.

Applications include sharing sweets, counting terms of the form in an expansion (see the binomial theorem) and counting outcomes of dice sums. The same counts appear in the hockey-stick identity and in Vandermonde's identity.

What is it used for?

Stars and bars counts the ways to share identical items among groups.

How to use distributing identical objects (≥ 1 each)

  1. Identify the number of objects and the number of groups .
  2. If each group needs at least one, use .
  3. If groups can be empty, use .
  4. Shift variables for other minimum sizes.

Graph

Positive solutions of x + y + z = n: C(n − 1, 2) for n = 3 to 8n = 6: 10n = 8: 210123456705101520Positive solutions of x + y + z = n: C(n − 1, 2) for n = 3 to 8n − 2yGraph with x from 0 to 7 and y from 0 to 24. Shows bars (6); point n = 6: 10 at (4, 10); point n = 8: 21 at (6, 21).

The counts are the triangular numbers 1, 3, 6, 10, 15, 21.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: sweets

In how many ways can 10 identical sweets be given to 4 children, each getting at least one?

Worked example
Answer
8484
  1. Formula
  2. Evaluate

Example 2: positive solutions

How many positive integer solutions has ?

Worked example
Answer
5555
  1. Formula
  2. Evaluate

Example 3: allowing zero

How many non-negative integer solutions has ?

Worked example
Answer
4545
  1. Formula
  2. Evaluate

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

x₁ + x₂ + x₃ = 10, xᵢ ≥ 1

C(9, 2)

36.

xᵢ ≥ 0

C(12, 2)

66.

k = 4, n = 8, xᵢ ≥ 1

C(7, 3)

35.

k = 4, n = 8, xᵢ ≥ 0

C(11, 3)

165.

Word problems

Positive integer solutions of x₁ + … + x_k = n number C(n − 1, k − 1); non-negative solutions number C(n + k − 1, k − 1).

Positive

x₁ + x₂ + x₃ = 10.

  1. C(9, 2)
  2. Check: ✓36

Non-negative

Same equation, xᵢ ≥ 0.

  1. C(12, 2)
  2. Check: ✓66

Four variables, positive Higher

x₁ + … + x₄ = 8.

  1. C(7, 3)
  2. Check: ✓35

Four variables, non-negative Higher

Same sum.

  1. C(11, 3)
  2. Check: ✓165

Common mistakes

Mixing the two formulae

C(n+k−1, k−1) for positive ✗

C(n−1, k−1) ✓

Positive vs non-negative.

Distinct objects

same ✗

identical only ✓

Stars identical.

Wrong lower index

C(n, k) ✗

C(…, k − 1) ✓

k − 1 bars.

Forgetting limits

unbounded ✗

extra bounds need inclusion–exclusion ✓

Upper bounds.

Exam tips

  1. Positive: C(n−1, k−1).
  2. Non-negative: C(n+k−1, k−1).
  3. Shift by 1 to convert.
  4. k − 1 bars.
  5. Identical objects.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. Positive, n = 8, k = 3 Foundation

21

2. Non-negative, n = 8, k = 3 Foundation

45

3. Positive, n = 12, k = 4 Foundation

165

4. Non-negative, n = 6, k = 4 Higher

84

5. Positive, n = 5, k = 5 Higher

1

6. Non-negative, n = 5, k = 2 Higher

6

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Stars and bars
Counting method.
Positive solution
xᵢ ≥ 1.
Non-negative solution
xᵢ ≥ 0.
Composition
Ordered positive parts.
Identical objects
Indistinguishable.
Bar
Divider.

Frequently asked questions

How many positive solutions of x₁ + … + x_k = n?

C(n − 1, k − 1).

How many non-negative solutions?

C(n + k − 1, k − 1).

How are the two linked?

Substitute yᵢ = xᵢ + 1.

Are the objects distinguishable?

No, identical.

Which page covers expected values of dice?

expected value of a die roll and of the max of two dice.

Which page covers circular arrangements?

circular arrangements.

More in Competition and admissions maths and the formula sheets.