Up: Student Seminars for 2015
Top: Math Department Student Seminars

Words Within Words

A Recursive Approach to Catalan Numbers and Fine Numbers


Professor David Vella

October 20, 2015
5:00 pm
Bailey Hall 207

Refreshments will be served in Bailey Hall 204 4:45pm


In this talk, I present a new recursive formula for the Catalan numbers. The proof uses Dyck words, one of the many objects known to be counted by the Catalan numbers. Dyck words are strings of two distinct symbols – such as A and B – such that no initial segment contains more B’s than A’s. Thus, AABABB is a Dyck word of length 6, but ABBABA is not, because the initial segment ABB has too many B’s. It is well known that the number of Dyck words of length 2n is given by C_n, the nth Catalan number. We obtain our recursion by “factoring” Dyck words into smaller Dyck words which appear inside them. While this proof is a very satisfying combinatorial proof of our recursion, we actually present a second proof, using generating functions, because this approach can be modified to yield a new formula that expresses the nth Fine number in terms of the Catalan numbers.

For additional information, send e-mail to math@union.edu or call (518) 388-6246.
Up: Student Seminars for 2015
Top: Math Department Student Seminars

Union College Math Department Home Page
Comments to: math@union.edu
Created automatically on: Fri Apr 20 21:52:36 EDT 2018