You are here

Catalan Numbers With Applications

Thomas Koshy
Publisher: 
Oxford University Press
Publication Date: 
2009
Number of Pages: 
422
Format: 
Hardcover
Price: 
125.00
ISBN: 
9780195334548
Category: 
Monograph
[Reviewed by
Andrew Niedermaier
, on
01/25/2009
]

Most mathematicians first meet the Catalan numbers Cn 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 {Cn}.

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 Cn. Topics like divisibility and various recursion triangles help give the reader an idea of how Cn arises as a “base case” in many larger problems. I particularly enjoyed seeing Cn appear as coefficients in determining the expected length of a best-of-(2n-1) baseball series.

The book finishes by exploring various generalizations of Cn 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 — C88 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 Cn is via Dyck paths. He can be reached via email at aniederm@math.ucsd.edu.

The table of contents is not available.

Dummy View - NOT TO BE DELETED