Catalan, Motzkin, and Riordan numbers

Catalan numbers C-n are widely known and studied and more recently the Motzkin numbers M-n have been celebrated. Closely joined to the Motzkin sequence is a sequence of unnamed numbers gamma(n), also growing in importance. Here they are denoted by R-n, where R stands for Riordan. In 1977, using the planar coloring schemes defined by W. T. Tutte, I discovered that these numbers answer an old problem about linearly independent chromatic polynomials. Planar coloring schemes for an n-ring can be viewed as the subset of cyclically spaced noncrossing partitions of an n-cycle, and they define a natural geometric basis for chromatic polynomials on the n-ring. This article presents a unified overview of Catalan, Motzkin, and R-numbers, intended as a primer of sequences and techniques, combinatorial structure and recursion, generating function equations, difference triangles, and Lagrange inversion. Direct combinatorial correspondences are highlighted. (C) 1999 Published by Elsevier Science B.V. All rights reserved.