Catalan Numbers With Applications

Most mathematicians first meet the Catalan numbers C_n late in their undergraduate career, often in a discrete math course. Many who go on to take a graduate-level combinatorics course probably know of Stanley’s exercise in Enumerative Combinatorics, Vol. 2, in which the reader is tasked with proving that each of 66 different combinatorial sequences is equal to {C_n}.

Thomas Koshy’s new book, Catalan Numbers With Applications, is a fascinating tour through through many of those exercises, but also of the myriad ways in which the Catalan numbers connect to other sequences and phenomena.

Catalan Numbers With Applications begins by familiarizing the reader with several identities relating to binomial coefficients (as well as focusing on properties of the central coefficients, 2n-choose-n). A few large chapters early on spend time recounting some of the more popular Catalan formulations: Dyck paths, nested parentheses, stacked circles, etc. Pictures, proofs, and calculations are provided throughout the book, making it accessible to a wide range of readers. Sprinkled throughout the chapters of the book are short biographies of important figures in discrete mathematics, a feature that provides the book with a strong perspective on the development of the subject.

Later in the book the focus shifts to properties and extensions of C_n. Topics like divisibility and various recursion triangles help give the reader an idea of how C_n arises as a “base case” in many larger problems. I particularly enjoyed seeing C_n appear as coefficients in determining the expected length of a best-of-(2n-1) baseball series.

The book finishes by exploring various generalizations of C_n and investigating tribinomial coefficients. By the end of the book many theorems are given without full proofs (just sketches or references). An appendix contains primers on topics such as inclusion-exclusion, generating functions, and induction. It also contains the first 100 Catalan numbers — C₈₈ is the first multiple of 1000, apparently — for those of us who have a supercomputer on hand and would like to verify any of this book’s manifold examples for the first 100 values.

Andy Niedermaier is a graduate student at the University of California, San Diego, specializing in combinatorics. When he isn’t cobbling together his thesis, he volunteers as a problem-writer for various math contests. His favorite definition of C_n is via Dyck paths. He can be reached via email at aniederm@math.ucsd.edu.