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 C_{k}(n) as

When k = 2 we find that C_{2}(n) = C_{n}, our familiar nth Catalan number. For k = 1 we have C_{1}(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 ...