Showing posts with label Dyck paths. Show all posts
Showing posts with label Dyck paths. Show all posts

Wednesday, 2 June 2021

The Fine Numbers

The Fine numbers and the Catalan numbers are intimately related. Two manifestations are the identity \(C_n=2F_n+F_{n−1} \text{ where }n \geq 1\), and the generating function identities:$$F(x)=\frac{C(x)}{1 +x \,C(x)} \text{ and }C(x)=\frac{F(x)}{1−x\,F(x)}$$This information is taken from the abstract to this 2001 paper titled A Survey of the Fine Numbers. However, I'm getting ahead of myself. How did I get here? Well, today I turned 26356 days old and one of the sequences to which this number belongs is OEIS A119012:


 A119012

Number of valleys strictly above the x-axis in all hill-free Dyck paths of semilength \(n\) (a hill in a Dyck path is a peak at level 1).


The members of this sequence increase rapidly on the way to 26356 (where \(n=10\), starting from \(n=1\)): 0, 0, 1, 5, 23, 98, 405, 1644, 6604, 26356, ...

The reference to Dyck paths immediately ties this number to the Catalan numbers that I've written about before on two difference occasions:
To quote from the Wikipedia article on Catalan Numbers (\(C-n\) is the \(n\)-th Catalan number):
\(C_n\) is the number of ways to form a "mountain range" with \(n\) upstrokes and \(n\) downstrokes that all stay above a horizontal line. The mountain range interpretation is that the mountains will never go below the horizon.

Figure 1 is the accompanying diagram to the previous text:

Figure 1

The depictions of "mountain ranges" are Dyck paths and can be written textually as:

  • \(n=1\): UD
  • \(n=2\): UDUD and UUDD
  • \(n=3\): UDUDUD, UDUUDD, UUDDUD, UUDUDDD and UUUDDD

The first Catalan numbers for \(n = 0, 1, 2, 3, \dots\) are 1, 1, 2, 5 (see Figure 1), 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, ... .

For Dyck paths, a peak of height one is also known as a hill and is represented as UD. It turns out that the Fine numbers count the number of Dyck paths having no hills. The Fine numbers begin: 1, 0, 1, 2, 6, 18, 57, ... beginning with \(n=0\).

Figure 2 shows the two Dyck paths with no hills for the case \(n=3\).


Figure 2

Getting back to OEIS A119012 (0, 0, 1, 5, 23, ... ) starting with \(n=1\), it can seen that there is only a valley in the case of \(n=3\) and that is confirmed by Figure 2.

There are generating functions for the Catalan numbers, the Fine numbers and the numbers making up OEIS A119012. The generating function for the Catalan numbers is:$$C(x)=\frac{1-\sqrt{1-4x}}{2x}$$For the Fine numbers, the generating function is:$$F(x)=\frac{1-\sqrt{1-4x}}{x\,(3-\sqrt{1-4x})}$$For OEIS A119012, the generating function is:$$G(x)= \frac{2 \left (1-3x-(1-x)\sqrt{1-4x}\right )}{\left (1+2x+\sqrt{1-4x}\right )^{2}\sqrt{1-4x}}$$Figure 3 shows the SageMath code for these generating functions:


Figure 3: permalink

Wednesday, 30 September 2015

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