You are here

Catalan Numbers With Applications

Publisher: 
Oxford University Press
Number of Pages: 
422
Price: 
125.00
ISBN: 
9780195334548

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.

Date Received: 
Tuesday, November 25, 2008
Reviewable: 
Yes
Include In BLL Rating: 
No
Thomas Koshy
Publication Date: 
2009
Format: 
Hardcover
Audience: 
Category: 
Monograph
Andrew Niedermaier
01/25/2009
Publish Book: 
Modify Date: 
Sunday, January 25, 2009

Dummy View - NOT TO BE DELETED