Skip over navigation
$ 1$, $ 1$, $ 2$, $ 5$, $ 14$, $ 42$, $ 132$, $ 429$, $ 1430$, $ 4862$ ,...
The Catalan numbers describe things such as:
The Catalan numbers are also generated by the recurrence relation:
$ C_0=1, \qquad C_n=\sum_{i=0}^{n-1} C_i C_{n-1-i}.$
For example, $ C_3=1\cdot 2+ 1\cdot 1+2\cdot 1=5$, $ C_4 = 1\cdot 5 + 1\cdot 2 + 2\cdot 1 + 5\cdot 1 = 14$, etc.
Walkabout
Age 14 to 16
Challenge Level 
Why do this problem
This
problem presents an investigation which does eventually require
a systematic approach. Although the generalisation is difficult for
Stage 4 some of the context's structure is discernible and
describable, and comparable to other similar situations. Do the
problem in conjunction with Group Photo and ask learners to
describe what is the same about the two situations that could
explain them resulting in the same sequence of Catalan numbers.An
apparent generalisation related to cubes of numbers breaks down and
so the problem offers an opportunity to discuss a danger of
applying inductive reasoning.
Possible approach
One approach is to do this in conjunction with Group
Photo , either following from one to the other, or dividing the
class so that groups work on different problems, or why not use two
classes working on the different problems. The aim would be to
bring the two sets of findings together to discuss why two
apparently quite different situations result in the same
mathematics.
Allow plenty of time to 'play' with the problem, making sense
of what is being counted and how it might be represented.
Encourage ideas that involve systematic approaches, and share
them so that all learners have access to a way into the
problem.
Use results from separate groups to check working.
Key Questions
- Can you describe what is the same about the two problems that might explain the similar mathematical structure?
- What is different about and what is similar to other examples, such as One Step Two Step and Room Doubling that result in a Fibonacci sequence?
Possible support
Group photo can be done with real people and you can start with small numbers. Spend plenty of time trying out, and considering the efficiency of, possible recording methods.Possible extension
Can students make connections between the structures of the two problems that may in part explain the mathematical connections?Notes
$ 1$, $ 1$, $ 2$, $ 5$, $ 14$, $ 42$, $ 132$, $ 429$, $ 1430$, $ 4862$ ,...
The Catalan numbers describe things such as:
- the number of ways a polygon with n+2 sides can be cut into n triangles
- the number of ways to use n rectangles to tile a stairstep shape (1, 2, ..., n-1, n)
- the number of ways in which parentheses can be placed in a sequence of numbers to be multiplied, two at a time
- the number of planar binary trees with n+1 leaves
- the number of paths of length 2n through an n-by-n grid that do not rise above the main diagonal
The Catalan numbers are also generated by the recurrence relation:
$ C_0=1, \qquad C_n=\sum_{i=0}^{n-1} C_i C_{n-1-i}.$
For example, $ C_3=1\cdot 2+ 1\cdot 1+2\cdot 1=5$, $ C_4 = 1\cdot 5 + 1\cdot 2 + 2\cdot 1 + 5\cdot 1 = 14$, etc.
You may also like
Doodles
Draw a 'doodle' - a closed intersecting curve drawn without taking pencil from paper. What can you prove about the intersections?
Russian Cubes
I want some cubes painted with three blue faces and three red faces. How many different cubes can be painted like that?
