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:

• Catalan Numbers on September 30th 2015
• Sums of Squares of Integers and Catalan Numbers on April 15th 2018

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