Skip to content Skip to navigation

Words within Words - A Recursive Approach to the Catalan Numbers and Fine Numbers

Event Type: 
David Vella, Skidmore College
Event Date: 
Tuesday, October 3, 2017 -
3:30pm to 4:30pm
SMLC 356
General PublicFaculty/StaffStudentsAlumni/Friends
Undergraduate Math Club

Event Description: 

Abstract: In this talk, I present a new recursive formula for the Catalan numbers. The proof uses Dyck Words, one of the many objects that are 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, since 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 Cn, the nth Catalan number. We obtain our recursion by "factoring" Dyck words into smaller Dyck words which appear inside them. We also present a second proof using generating functions. The generating function approach can be modified to yield a new formula that expresses the nth Fine number in terms of the Catalan numbers.

Event Contact

Contact Name: Monika Nitsche

Contact Email: