Combinatorics path · C11

Before this lesson: Basic counting principles, Recursive sequences, Mathematical induction: the first principle

Your goal: Derive a recurrence from a disjoint partition of objects.

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.

Counting with recurrences: the key idea

A counting recurrence divides objects of size n into disjoint cases that reduce to smaller objects. Condition on the final step, first tile or a distinguished position, and prove that removing it gives a reversible construction. Include enough initial cases, often including the empty object. The recurrence counts the class only when every object falls into exactly one case; overlapping or missing cases invalidate it.

A worked example

Count tilings of a 1×n board using monominoes of length 1 and dominoes of length 2.

Let Tₙ be the count, with T₀=1 and T₁=1. A tiling begins with either a monomino, leaving n−1 cells, or a domino, leaving n−2. These disjoint cases give Tₙ=Tₙ₋₁+Tₙ₋₂ for n≥2. Thus T₂=2,T₃=3,T₄=5.

Your turn: change one thing

Count binary strings of length n with no consecutive ones.

Try this on paper before opening the explanation.

Compare your reasoning

Let S₀=1,S₁=2. A valid string ends in 0 after any valid length n−1 string, or in 01 after any valid length n−2 string for n≥2. Thus Sₙ=Sₙ₋₁+Sₙ₋₂; in the second case n=2 includes prefix length zero.

Pause and check

A trap to avoid: Writing a recurrence whose cases overlap or miss a boundary case.

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

Justify the tiling recurrence without relying on a drawing alone.

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

Every tiling has exactly one first tile. If it has length 1, removing it gives a unique tiling of length n−1; if length 2, removing it gives one of length n−2. Conversely, adding the chosen first tile recovers the original. The two classes are disjoint and exhaustive, so their counts add.

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. Why must the recurrence cases be disjoint?

Foundation

  1. To make all cases equally large
  2. To avoid initial values
  3. To force a geometric sequence
  4. To avoid counting an object more than once
Hint

Each object should belong to one case.

Answer and reasoning

To avoid counting an object more than once. Overlapping cases would be counted repeatedly when their sizes are added.

2. How many tilings does an empty board have in the usual recurrence?

Foundation

  1. 0
  2. 2
  3. Undefined
  4. 1
Hint

There is one empty tiling.

Answer and reasoning

1. This base makes adding a single domino to an empty remainder count correctly.

3. Tilings of a 1×4 board with lengths 1 and 2: count?

Core

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

Build 1,1,2,3,5 from indices 0 to 4.

Answer and reasoning

5. T₄=T₃+T₂=3+2=5.

4. Binary strings of length 3 with no consecutive ones: count?

Core

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

Use S₀=1,S₁=2.

Answer and reasoning

5. S₂=3 and S₃=3+2=5.

5. For a tiling beginning with a domino, what remains?

Stretch

  1. A board of length n−1
  2. Two independent boards always
  3. No valid tiling
  4. A board of length n−2
Hint

The domino covers two cells.

Answer and reasoning

A board of length n−2. Removing the first domino leaves a single board of length n−2.

6. Why verify reversibility of the reduction?

Stretch

  1. To prove each smaller object reconstructs exactly one object in that case
  2. To reverse every number
  3. To avoid proving coverage
  4. To change the initial values
Hint

The reduction must be a bijection for the count to be exact.

Answer and reasoning

To prove each smaller object reconstructs exactly one object in that case. A reversible construction prevents both missing objects and multiple preimages.

7. A recurrence’s initial values should include what?

Foundation

  1. Only prime indices
  2. Enough small cases to start its rule
  3. Only one random large case
  4. No empty object ever
Hint

Check every backward reference.

Answer and reasoning

Enough small cases to start its rule. The first recurrence evaluation must refer only to defined earlier values.

8. Tilings of length 5 with tiles 1 and 2: count?

Core

  1. 13
  2. 8
  3. 5
  4. 10
Hint

Use T₅=T₄+T₃.

Answer and reasoning

8. The preceding counts are 5 and 3, so the answer is 8.

9. Why is the empty prefix allowed in the binary-string recurrence?

Stretch

  1. It produces valid shortest strings such as 01
  2. It adds an extra digit
  3. It counts an invalid string
  4. It makes every count zero
Hint

The empty object has one construction.

Answer and reasoning

It produces valid shortest strings such as 01. For n=2, the suffix 01 follows a length-zero valid prefix.

Choose your next step

Continue to Inclusion–exclusion. 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.