An investigation of the sequence of Catalan numbers with activities for prospective teachers

School Science and Mathematics, Jan 1998 by Koker, John, Kuenzi, Norbert J, Oktac, Asuman, Leibowitz, Rochelle, Carmony, Lowell

In The Handbook of Integer Sequence Numbers by N. J. Sloane (1973), the sequences of integers known as the Catalan numbers and the Bell numbers are called sequences 577 and 585, respectively. In this paper, several problems in which these sequences arise are investigated. These problems are appropriate for both pre- and in-service teachers, as well as students studying discrete mathematics.

In the year 1202, a mathematician named Leonardo of Pisa, known more commonly as Fibonacci (son of Bonaccio), published the work Liber Abaci, which translates as Book of the Abacus. In this book, Fibonacci demonstrated algebraic methods and problems in which the use of Hindu-Arabic numerals was strongly advised. One problem in this book that has kept the interest of students of mathematics for centuries is the following: "How many pairs of rabbits will be produced in a year, beginning with a single pair, if in every month each pair bears a new pair which becomes productive from the second month on?" This famous problem gives rise to the sequence, known as the Fibonacci Sequence; 1,1, 2, 3, 5, 8,13, 21, ..., F^sub n^,, ...,where F^sub n^ = F^sub n-1^ F^sub n-2^ and F^sub 0^ = F^sub 1^ = 1. This sequence has many beautiful, significant properties and arises in the strangest of places. For more information on Fibonacci and the Liber Abaci, see Boyer and Merzbach (1989).

A "Fibonacci-like" sequence of numbers was discovered by Leonhard Euler (1707-1783) while working on the problem of triangulating polygons. This sequence was rediscovered in 1838 by Eugene Catalan, and it now bears his name. It is discussed extensively later in this paper.

Problems whose solutions end up being a sequence of numbers following a specific pattern are popular in mathematics courses for prospective elementary teachers. This article describes problems that help preservice teachers investigate some number patterns. The class should be divided into groups of three or four, and the following five problems should be discussed briefly before the entire class. Each group, then, should work on one assigned problem and, after sufficient time, be able to report its results to the class. Any group completing its assigned problem early should be invited to work on the next problem to provide a means of checking other groups' work.

Each problem can be started by looking at small cases. Once these cases are understood, students should see patterns and make conjectures about the general solution. Appropiate manipulatives are helpful in visualizing and constructing the objects described in the problem.

The Problems

Geoboard Walks

Consider an n x n geoboard ABCD with a rubberband connecting the corners A and C to form a diagonal "railroad track," as shown in Figure 1.

Count the number of distinct paths you can take from A to C that are composed of unit blocks (moving right, "east," or up, "north"), without crossing the railroad tracks. That is, the walk may touch the diagonal from A to C but never go "above it" or "across it." Start with n = 1, 2, 3, ... and generalize your results. Figure 2 shows examples of two different paths for the case n = 5. The walks can be described using strings of Es (for east) and Ns (for north). The one on the left is EEENNNEENN, while the one on the right is EENENEENNN.

Associativity Groups

For a given product of n fixed terms, how many ways are there to associate these terms without changing the order in which they appear? Note that by "associating the terms in a product," we mean inserting parentheses so that every inner grouping is the multiplication of exactly two factors. Two examples of associating the terms in the product abcd (n = 4) are ((a(bc))d) and ((ab)(cd)). Try for n = 2, 3, 4, ... and generalize your results.

Rhyming Patterns

We say that the lines of a stanza rhyme with each other if the last words of the lines rhyme. How many different rhyming patterns are possible for a stanza with n lines? Start with n = 1, 2, 3, ... and generalize your results. Here are examples of two different rhyming patterns for 4-line stanzas:

Hey Koker,

You wanna play poker?

Probably not,

Since you're just a joker.

I am an owl

Who is calling me?

Must be a towel

That happens to talk.

In the first poem, the first, second, and fourth lines rhyme with each other; the third one stands alone. In the second, the first and third lines rhyme with each other, and the second and fourth lines stand alone. Note that a pattern where none of the lines rhyme with each other is also a possibility. Students can model any pattern using colored counters. Each counter represents a line. Counters that are the same color represent rhyming lines.

Polygon Triangulations

Find the number of ways a given convex n-gon can be triangulated (subdivided into triangles) by drawing diagonals that do not intersect. (See Figure 3.) These triangulations can be modeled on geoboards. Note that two triangulations are not equivalent if they use different vertices, even if they might be congruent to each other.