Combinatorics path · C06

Before this lesson: Factorials, Basic counting principles

Your goal: Choose a representation that enforces the restriction without duplicate counting.

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.

Names you may know: permutations with repeated letters; restricted permutations.

Permutations and arrangements: the key idea

A permutation is an ordered arrangement. Distinct objects in a row have n! orders. If identical types occur with multiplicities m₁,…,mₖ, divide by ∏mi!\prod m_{i}! because exchanging identical copies does not change the arrangement. For adjacency restrictions, combine a required consecutive group into a block, then count its internal orders. For separation restrictions, place one type first and choose gaps for the other. Lexicographic counting fixes a prefix and counts all smaller possible next symbols before continuing.

A worked example

How many distinct arrangements of the letters in LEVEL are there?

Five positions contain two Ls, two Es and one V. Labelled copies would give 5! arrangements, but each visible word occurs 2!·2! times. The answer is 5!/(2!2!)=30.

Your turn: change one thing

How many orders of A,B,C,D,E have A and B adjacent?

Try this on paper before opening the explanation.

Compare your reasoning

Treat AB as a block with two internal orders. The block and C,D,E give 4! orders. Multiply by 2 to obtain 48.

Pause and check

A trap to avoid: Dividing by factorials without a justified symmetry or treating overlapping blocks independently.

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 arrangements of four identical Xs and three identical Os with no two Os adjacent.

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 place XXXX. There are five gaps, including the two ends. To avoid adjacent Os, choose three distinct gaps and place one O in each. This is a reversible construction, so the count is C(5,3)=10.

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. Distinct linear arrangements of n different objects total what?

Foundation

  1. C(n,2)
  2. n!
  3. n
  4. 2n2^{n} always
Hint

Choose successive positions.

Answer and reasoning

n!. The product n(n−1)⋯1 equals n!.

2. Why divide by factorials for repeated letters?

Foundation

  1. The total number of letters changes
  2. Exchanging identical copies does not change the visible word
  3. Order is entirely ignored
  4. Some positions disappear
Hint

Labelled copies cause repeated counting.

Answer and reasoning

Exchanging identical copies does not change the visible word. Each visible word corresponds to the same number of relabellings within repeated types.

3. How many arrangements of LEVEL?

Core

  1. 60
  2. 20
  3. 30
  4. 120
Hint

Divide 5! by 2!2!.

Answer and reasoning

30. 120/4=30.

4. Orders of A,B,C,D,E with A,B adjacent?

Core

  1. 120
  2. 48
  3. 24
  4. 60
Hint

Count four objects including the block, then its internal order.

Answer and reasoning

48. 4!·2=48.

5. Four Xs create how many gaps including both ends?

Stretch

  1. 5
  2. 3
  3. 4
  4. 6
Hint

List the spaces around XXXX.

Answer and reasoning

5. There are three internal gaps and two end gaps.

6. Four identical Xs and three identical Os with no adjacent Os: count?

Stretch

  1. 20
  2. 35
  3. 5
  4. 10
Hint

Choose three of the five gaps.

Answer and reasoning

10. C(5,3)=10, with at most one O in each chosen gap.

7. An arrangement of distinct objects treats order as what?

Foundation

  1. Always circular
  2. Always repeated
  3. Significant
  4. Irrelevant
Hint

Swapping positions usually changes the outcome.

Answer and reasoning

Significant. Different orders are different permutations.

8. Distinct arrangements of AAB are how many?

Core

  1. 3
  2. 6
  3. 2
  4. 9
Hint

Divide 3! by the two A relabellings.

Answer and reasoning

3. The arrangements are AAB,ABA,BAA.

9. Why multiply by 2 when treating adjacent distinct A,B as one block?

Stretch

  1. The block can be AB or BA
  2. There are two other objects
  3. The table is circular
  4. Every block has size two by definition
Hint

Internal order still matters.

Answer and reasoning

The block can be AB or BA. Both internal orders produce different arrangements of the distinct letters.

Choose your next step

Continue to Circular permutations. 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.