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
They can be described by the formula $$\frac{ ^{2n}C_{n}
}{(n + 1)}$$
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.