Tuesday, January 5, 2010

odd Catalans

One thing that jumps out of the Catalan Number Triangle fractal is the infrequency and regular spacing of the odd Catalan numbers. The Catalan numbers show up in the right-most column of the Catalan Number Triangle, and the odd ones are the ones show up in black in the diagram above (those that are congruent to 1 mod 2 are displayed as black, and those congruent to 0 mod 2 are displayed as grey).

Mathworld tells us that odd Catalan numbers are those of the form $C_{2^k-1}$, in other words, the indicies of the odd Catalans are Mersenne numbers. The first bunch of odd-Catalans are 1, 5, 429, 9694845, ... (A038003 in OEIS).

Odd Catalans grow pretty rapidly. Coincidentally, there is an even more rapidly growing sequence known as the Catalan-Mersenne sequence (A007013 in OEIS). The Catalan-Mersenne sequence is not mathematically connected to the Catalan numbers - it is a subsequence of the Mersenne numbers which Catalan discovered, and is defined by this recursion:

The values of $c_n$ grow so quickly that OEIS only displays the first five terms.