A Surreptitious Sequence: The Catalan Numbers

When Alissa S. Crans spoke about the Catalan numbers at the MAA Carriage House on May 21, the Loyola Marymount professor titled her talk “A Surreptitious Sequence.”

Crans, though, proved every bit as sneaky as the sequence of numbers she’d chosen for her subject matter. Into an hour-long lecture ostensibly about the Catalans, she wove many lessons. The audience learned about the mathematical concept of sameness, the nature of mathematical research, and the error of assuming that a mathematical object was discovered by the mathematician whose name it bears.

Take the Catalan numbers, a surprisingly ubiquitous sequence of natural numbers that begins 1, 1, 2, 5, 14. The sequence is named for Belgian mathematician Eugène Catalan (1814-1894) even though it had cropped up in the work of Swiss mathematician Leonhard Euler 70 years earlier and, as Crans noted, was known to Chinese mathematicians long before that.

Euler came across the Catalan numbers while exploring a question about dividing convex polygons into triangles using non-intersecting diagonals. Crans, however, used two other examples to illustrate what it means for two questions to be the same in a mathematical sense.

Consider sequences of 1’s and -1’s such that there are the same number of 1’s as -1’s and all of the partial sums are nonnegative. How many such sequences are there if we permit ourselves one 1 and one -1? What about two of each? Three?

Next consider an even number of people seated at a round table. How many ways can simultaneous handshakes occur without anyone’s arms crossing?

It turns out that the Catalan numbers count both the sequences and the handshakes, which hints that the two situations are "the same." "The same," that is, just as a donut and a coffee mug are indistinguishable to a topologist because one can be deformed into the other without changing the number of holes.

“In the same way that a coffee cup and a donut are considered 'the same,' all these questions that we’ve talked about are considered the same to a mathematician,” Crans explained. “The way that we show that is we come up with a reversible process that goes from one of these to another. Mathematicians call this a bijection.”

Crans then demonstrated how to turn a handshake table into a sequence of 1’s and -1’s, and vice versa. To transform a table into a sequence she enlisted the help of “a very, very smart mathematical bug”—imaginary, of course. As the bug walks the circumference of the table, she shouts “one” when she encounters a handshake pair for the first time and “negative one” when she passes a pair the second time. The resulting sequence of 1’s and -1’s corresponds to the handshake table the bug circled and, you can verify, satisfies the partial sum condition noted above.

After finishing off the bijection and touching on examples involving Dyck paths and Poincaré duality, Crans connected the Catalan numbers to a familiar artifact of mathematics named as if it arose in 17th-century France: Pascal’s Triangle.

It turns out that the triangle was known hundreds of years earlier to Chinese mathematicians, Crans said.

Look at the rows of the triangle that have a middle number, Crans prompted listeners. Subtract from each middle number the number adjacent to it (left or right makes no difference, since they’re the same). What do you get? The Catalans. Likewise if you divide the entries in the middle column by the counting numbers.

“Why doesn’t everyone love mathematics?” Crans asked. “I mean, how cool is this?”

Of course Catalan keenness can lead you astray, as Crans showed near the end of her talk. She framed a question about the peg-and-disk puzzle Tower of Hanoi. Crans termed an arrangement of the puzzle’s disks “legal” if, in any stack of disks, disk diameter decreases moving upward. Crans asked how many legal arrangements could be created with different numbers of disks.

With one disk, there’s one arrangement; with two, there are two; with three, five. Sound familiar? Given time to draw out the possibilities, listeners had soon convinced themselves not only that they could construct 14 legal arrangements of four disks, but that the Catalan numbers had furnished the answer to yet another question.

But, alas, the audience had fallen prey to what Crans called “inductive reasoning gone wrong.” With five disks you can make not 42 legal arrangements (as the Catalan pattern would predict), but 41.

“It’s tantalizingly close,” Crans said.

So what is the relationship between the Catalan numbers and the Tower of Hanoi arrangements?

“Can we change this question that I posed in such a way that the Catalan numbers do wind up serving as an answer?” Crans asked.

This is how research proceeds in mathematics, she said, by incrementally modifying problems into new ones.

“Can we have more disks? Can we have more pegs? How can we change this problem just a little bit—tweak it—and then figure out the answer to that question?” —Katharine Merow

Watch a short version of the lecture on YouTube.

Listen to an interview with Alissa Crans and MAA Director of Publications Ivars Peterson (mp3)