Counting Recursively

Tilings, strings and brackets

An interactive lesson with 6 steps, about 5 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• Split by how an object ends (or begins) to find a recurrence.
• Domino tilings of a $2 \times n$ strip follow Fibonacci.
• Catalan numbers count balanced brackets, triangulations and trees.

Steps

1. Dominoes
2. Thirteen tilings
3. A longer strip
4. Balanced brackets
5. Four pairs
6. Triangulations