Chapter 35

Generalized Catalan Numbers

We know that for n ≥ 0, the nth Catalan number is given by


which can be rewritten as


But why would we want to do this?

If we let k denote a fixed positive integer, then we can define the generalized Catalan number Ck(n) as


When k = 2 we find that C2(n) = Cn, our familiar nth Catalan number. For k = 1 we have C1(n) = nn = 1, for n ≥ 0.

Corresponding to the cases for k = 3 and k = 4, we find the sequences


Based on what we have seen so far, it seems that these generalized Catalan numbers are all integers. This is indeed the case, as we shall now establish. Before doing so, however, we need to recall the following facts about the 291 system of integers:

1. If a and b are positive integers, then the greatest common divisor of a and b, denoted gcd (a, b), is the smallest positive integer that can be written as a linear combination of a and b—so there exist integers s and t with gcd (a, b) = as + bt and no smaller positive integer can be expressed in this manner.

2. If a and b are positive integers with gcd (a, b) = 1, then we say that a and b are ...

Get Fibonacci and Catalan Numbers: An Introduction now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.