Catalan Numbers

Today I turned \(24285\) days old and Figure 1 shows my Twitter post to commemorate the occasion:

Figure 1

The sequence referred to in the tweet is OEIS A178854 and its members, up to and including \(384733\), can be generated using the SageMath code shown in Figure 2.

Figure 2: permalink

The resultant output is: 1, 1, 5, 13, 29, 29, 93, 221, 221, 733, 1757, 3805, 7901, 7901, 24285, 57053, 122589, 122589, 384733, 384733.

Of course, it got me thinking about what a Catalan number is (let alone an odd Catalan number). It turns out that "the only Catalan numbers \(C_n\) that are odd are those for which \(n = 2^k − 1\). All others are even" (Wikipedia). But firstly, what are the Catalan numbers? Here is a definition from the same Wikipedia source where zero-based numbering is used and the \(n\)-th Catalan number is given by:$$C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} = \prod\limits_{k=2}^{n}\frac{n+k}{k} \qquad\text{for }n\ge 0$$The first Catalan numbers for n = 0, 1, 2, 3, ... are:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ... (sequence A000108 in the OEIS)

Note that when \(n =2^2-1=3, n = 2^3-1=7, n=2^4-1=15\) etc., the corresponding Catalan numbers are odd (\(5, 429, 9694845\)). The odd Catalan numbers form the OEIS A038003. Of interest here of course is the 15th Catalan number \(9694845\) and the fact that \(9694845 \! \! \mod 2^{15}= 24285\). 

An example of the practical applications of Catalan numbers is shown in Figure 3 (again taken from the Wikipedia article) illustrating their application to Dyck paths:

Figure 3

Of course there's a lot more to Catalan numbers than this and reading the Wikipedia article thoroughly as well the WolframAlpha entry is a start to understanding these numbers more deeply.

on December 19th 2020

There is a later post on April 15th 2018 titled
Sums of Squares of Integers and Catalan Numbers