Combinatorics path · C08

Before this lesson: Combinations and binomial coefficients, Permutations and arrangements

Your goal: Count partitions with correct group labels and size symmetries.

Start with the idea and one example. Take a break before the written task if you need it. The questions are original teaching exercises, not official past-paper questions.

Dividing Objects into Groups: the key idea

To distribute n distinct objects into labelled groups of fixed sizes n₁,…,nₖ summing to n, use n!/(n₁!⋯nₖ!). Within a group the order is ignored. If the groups themselves are unlabelled, identical-sized groups can be permuted without changing the partition, requiring further division by the factorial of the number of groups of each repeated size. Do not divide for labels that matter. First state whether objects, recipients and within-group positions are distinguishable.

A worked example

Split six distinct students into a labelled red team of two and blue team of four.

Choose the red team in C(6,2)=15 ways; the rest form the blue team. Equivalently the count is 6!/(2!4!)=15.

Your turn: change one thing

Split six distinct students into two unlabelled groups of three.

Try this on paper before opening the explanation.

Compare your reasoning

Choosing one triple gives C(6,3)=20, but every partition is counted twice because either triple may be chosen first. Divide by 2 to get 10.

Pause and check

A trap to avoid: Dividing by every group factorial even when group sizes differ.

Practise and adjust the level

Foundation checks the language; Core applies the method; Stretch asks you to choose or justify an idea. These are levels within this lesson. A session selects six of the nine questions; unused questions allow the level to change. Advanced theory still needs written practice.

Interactive practice loads here. You can also use the complete question set below.

Write a complete argument

Count partitions of six distinct objects into three unlabelled pairs.

Planning hint

List the assumptions and the exact conclusion. Identify the definition or theorem in this lesson that connects them. Explain why its conditions hold before using it.

Read the full solution after your attempt

First form three labelled pairs: 6!/(2!2!2!)=90. The three distinct pair-blocks can receive the labels in 3! ways, all producing the same unlabelled partition. Dividing gives 90/6=15.

My proof notebook

Write on paper, or keep a draft here. Compare your reasoning with the solution only after a real attempt. The checklist is your own review, not an automatic mark.

All nine practice questions

Prefer paper or have JavaScript switched off? The complete question set, hints and solutions are here. Interactive practice uses these same questions in an order chosen from your answers.

1. For labelled groups, do the recipient labels matter?

Foundation

  1. Only if sizes differ
  2. Only if objects repeat
  3. Yes
  4. No
Hint

Swapping groups between recipients can change the outcome.

Answer and reasoning

Yes. Assignments to different labelled groups are distinct.

2. Within-group order is ignored by dividing by what?

Foundation

  1. Each group size factorial
  2. The total size only
  3. Every label
  4. 2 always
Hint

Permutations within a group represent the same group.

Answer and reasoning

Each group size factorial. Divide by n₁!⋯nₖ! for fixed group sizes.

3. Six students into labelled groups of sizes 2 and 4: count?

Core

  1. 90
  2. 15
  3. 30
  4. 10
Hint

Choose the two-person group.

Answer and reasoning

15. C(6,2)=15.

4. Six students into two unlabelled triples: count?

Core

  1. 40
  2. 10
  3. 20
  4. 15
Hint

Each partition is counted twice by choosing a triple.

Answer and reasoning

10. C(6,3)/2=10.

5. Six distinct objects into three unlabelled pairs: count?

Stretch

  1. 45
  2. 15
  3. 90
  4. 30
Hint

Divide the labelled-group count by 3!.

Answer and reasoning

15. 6!/(2!³3!)=15.

6. Why not divide by 2 for a labelled red and blue split?

Stretch

  1. All groups must be unlabelled
  2. The sizes are prime
  3. Factorials cannot be divided
  4. Exchanging red and blue changes the assignment
Hint

The labels are part of the outcome.

Answer and reasoning

Exchanging red and blue changes the assignment. A different recipient assignment is a different distribution.

7. A partition of a set places each object in how many blocks?

Foundation

  1. Exactly one
  2. At least two
  3. Zero only
  4. Any number
Hint

Blocks are disjoint and cover the set.

Answer and reasoning

Exactly one. Each object belongs to one block of the partition.

8. Four distinct objects into two unlabelled pairs: count?

Core

  1. 6
  2. 12
  3. 2
  4. 3
Hint

Choose a pair and divide by the two group orders.

Answer and reasoning

3. C(4,2)/2=3.

9. Why divide by 3! for three equal-sized unlabelled groups?

Stretch

  1. Every group has three objects
  2. Within-group order matters
  3. Permuting the group labels preserves the same partition
  4. The objects are identical
Hint

Each partition has six labelled versions.

Answer and reasoning

Permuting the group labels preserves the same partition. The three distinct blocks can receive the three temporary labels in 3! ways.

Choose your next step

Continue to Counting integer solutions. If this felt difficult, return to a prerequisite above. Every lesson stays open.

Open my revision list →

Original teaching material · IMOolympiad.com. Send a specific correction through our contact page. Learning progress is optional and stays in this browser.