# A Fine sequence with fine interpretations

The ubiquitous Catalan numbers $$\C_n\$$ count the number of Dyck paths, sequences of up-steps and down-steps of length $$\2n\$$ that start and end on a horizontal line and never go below said line. Many other interesting sequences can be defined as the number of Dyck paths satisfying given conditions, of which the Fine sequence $$\F_n\$$ (not the Fibonacci numbers and not related to any common definition of "fine") is one.

Let a hill be a sequence of an up-step followed by a down-step that starts – and therefore also ends – on the horizontal line. $$\F_n\$$ is then the number of Dyck paths of length $$\2n\$$ with no hills. The picture below illustrates this: there are $$\C_5=42\$$ Dyck paths of length $$\10\$$, of which $$\F_5=18\$$ (marked in black) have no hills. This sequence is OEIS A000957 and begins $$\begin{array}{c|ccccccccccc} n&0&1&2&3&4&5&6&7&8&9&10\\ \hline F_n&1&0&1&2&6&18&57&186&622&2120&7338 \end{array}$$ $$\begin{array}{c|ccccccccccc} n&11&12&13&14&15\\ \hline F_n&25724&91144&325878&1174281&4260282 \end{array}$$

Other things counted by the Fine numbers include

• the number of Dyck paths of length $$\2n\$$ beginning with an even number of up-steps
• the number of ordered trees with $$\n+1\$$ vertices where the root has no leaf children
• the number of ordered trees with $$\n+1\$$ vertices where the root has an even number of children
• and so on. For more interpretations see Deutsch and Shapiro's "A survey of the Fine numbers".

## Formulas

You may use any correct formula to generate the sequence. Here are some:

• The generating function is $$\sum_{n=0}^\infty F_nz^n=\frac1z\cdot\frac{1-\sqrt{1-4z}}{3-\sqrt{1-4z}}$$
• For $$\n\ge1\$$, $$\C_n=2F_n+F_{n-1}\$$.
• An explicit formula: $$F_n=\frac1{n+1}\sum_{k=0}^n(-1)^k(k+1)\binom{2n-k}{n-k}$$

Standard rules apply to this challenge, where permissible behaviours are

• outputting the $$\n\$$th term in 0- or 1-based indexing given $$\n\$$
• outputting the first $$\n\$$ terms given $$\n\$$
• outputting the infinite sequence with no input, either by printing or returning a lazy list/generator

This is ; fewest bytes wins.

# Python 2, 58 bytes

i=a=1;b=0
while 1:print a;i+=1;a,b=2*b+7*a/2-(2*a+b)*3/i,a


Try it online!

Prints the sequence endlessly. The method substitutes $$\C_n = 2F_n + F_{n-1} \$$ into the Catalan recurrence $$C_n = 4C_{n-1} - \left\lfloor \frac{6C_{n-1}}{n+1} \right\rfloor$$

• @dingledooper awesome. I think you should post your own answer, it's sufficently different (and more clever) Feb 23 at 1:56

# Vyxal, 2210 7 bytes

-12 bytes by emanresu A (double welp)
-3 bytes by alephalpha using a clever approach

ꜝ$ʀƈ¦ṁȧ  Try it Online! How it works ꜝ$ʀƈ¦ṁȧ
ꜝ\$               Bitwise not n and swap with input
ʀƈ             Take the binomial coefficient
¦ṁȧ          Cumultative sum, take the mean and push the absolute value

• 15 Feb 22 at 10:16
• @emanresuA ... wth man Feb 22 at 10:42
• 10 (several tricks stolen from Unrelated String) Feb 22 at 11:27
• 7 Feb 24 at 9:11

# HOPS, 19 bytes

C=1+x*C^2;C/(1+x*C)


Attempt This Online!

The generating function of the Catalan numbers satisfies $$\C(x)=1+x\ C(x)^2\$$. The generating function of this sequence is $$\F(x)=C(x)/(1+x\ C(x))\$$.

# HOPS, 21 bytes

2/(1+2*x+sqrt(1-4*x))


Attempt This Online!

A simplified version of the generating function.

It seems that HOPS on ATO is currently not working.

# Python 3, 61 bytes

f=lambda n,v=1:sum(f(i,0)*f(n+~i,v)for i in range(v,n))or 1-n


Try it online!

# JavaScript (Node.js), 50 bytes

f=(n,v=1,i=v)=>i<n?f(i,0)*f(n+~i,v)+f(n,v,i+1):+!n


Try it online!

Another 47 bytes JavaScript answer but output true and false for f(0), f(1).

First, we write down following recursive formula:

$$F_n=\sum_{i=1}^{n-1}C_i\cdot F_{n-i-1}$$ $$F_1=0, F_0=1$$ $$C_n=\sum_{i=0}^{n-1}C_i\cdot C_{n-i-1}$$ $$C_0=1$$

Then, we try to merge two functions into one

$$f(x,1):=F_x$$ $$f(x,0):=C_x$$ $$f(x,v)=\begin{cases}\sum_{i=v}^{x-1}f(i,0)\cdot f(x-i-1,v) & x>v\\ 0 & x=v=1 \\ 1 & x=0 \end{cases}$$

# JavaScript (ES6), 48 bytes

Returns the $$\n\$$-th term (0-indexed).

Inspired by the Catalan recurrence pointed out by Sisyphus.

f=n=>n?(g=n=>n?g(n-1)*(4+6/~n):1)(n)-f(n-1)>>1:1


Try it online!

# JavaScript (ES6), 60 bytes

Returns the $$\n\$$-th term (0-indexed).

This is based on the explicit formula provided in the challenge.

f=(n,k=n)=>~k&&(g=v=>v--?(v-n-k)*g(v)/~v:--k-n)(k)/~n-f(n,k)


Try it online!

# Jelly, 12 11 bytes

ḤrcµJNÐeḋ:L


Try it online!

Port of emanresu A's golf to mathcat's Vyxal solution.

Ḥrc            Each of [2n .. n] choose n.
µ    ḋ      Take the dot product of that with
J          [1 .. n+1]
NÐe       with every other element negated,
:     and (floor) divide that by
µ      L    n+1.


# Jelly, 18 bytes

o2µḤœcµṬ-*ÄAƑ×ṂḂ)S


Try it online!

Haven't actually tried any closed form or recursive formulae, but ignoring the special case fix for $$\n=0\$$ this brute-force enumeration feels elegant enough to post, especially considering how the current golflang closed form solutions are. Leverages the "even number of leading up-steps" interpretation--or rather, "first down-step at an odd 1-index", hence the special case.

o2µ                   If n is 0, from here on out, pretend it's 2.
œc                Get every combination of n elements from
Ḥ                  [1 .. 2n],
µ         )     then for each combination:
Ṭ-*            Produce a list of -1 at those indices and 1 elsewhere,
Ä           take its cumulative sums,
AƑ         and check that none of those is negative.
×        Multiply that result by
Ṃ       the smallest element of the combination.
Ḃ S    How many are odd?

• Why is the 12-byter funnier? Feb 22 at 11:08
• @ParclyTaxel Explanation pending Feb 22 at 11:09
• Wow, nice port! I tried porting it to Jelly but couldn't find the binomial coefficient builtin. Feb 22 at 11:21

# 05AB1E, 2221 14 bytes

xŸIc2Å€(}ηOÅAÄ


Port of @mathcat's Vyxal answer, so make sure to upvote him as well!

Uses the formula: $$G_{n,k} = (-1)^{(k+1)}\binom{k}{n} + G_{n-1,k}\\ F_n=\left|\frac{1}{n+1}\sum_{k=n}^{2n}G_{n,k}\right|$$
Given $$\n\$$, it'll output $$\F_n\$$.

Explanation:

x              # Push double the (implicit) input (without popping)
Ÿ             # Pop both, and push a list in the range [input,2*input]
Ic           # Calculate the bionomical coefficient of each value with the input
2Å€(}      # Negate every second item, starting with the first:
2          #  Push a 2
Å€ }      #  Map over each item where the 0-based index is divisible by 2:
(       #   Negate that item
ηO    # Calculate its cumulative sum:
η     #  Get all prefixed of this list
O    #  Sum each inner prefix-list together
ÅA  # Get the arithmetic mean of that
Ä # Convert it to its absolute value
# (after which it is output implicitly as result)


ÝεÈ·<y>Ixs‚y-cI>zP}O


-1 byte thanks to @emanresuA

Uses the given explicit formula: $$F_n=\sum_{k=0}^n(-1)^k(k+1)\binom{2n-k}{n-k}\frac1{n+1}$$
Given $$\n\$$, it'll output $$\F_n\$$.

Explanation:

Ý              # Push a list in the range [0, (implicit) input]
ε             # Map each integer to:
È            #  Check whether it's even
·           #  Double that check (2 if even; 0 if odd)
<          #  Decrease it by 1 (1 if event; -1 if odd)
y>           #  Push the current integer, and decrease it by 1
I            #  Push the input
x           #  Double it (without popping)
s‚         #  Swap, and pair them together: [2n,n]
y-       #  Subtract the current integer from each: [2n-k,n-k]
#  Pop and push the values back to the stack
c     #  Calculate their binomial coefficient
I>z          #  Push 1/(input+1)
P            #  Take the product of the four values on the stack
}O            # After the map: sum them together
# (after which the result is output implicitly)

• I don't know 05AB1E but this seems to work? Feb 22 at 10:20
• @emanresuA Thanks. And porting mathcat's Vyxal answer is even 7 bytes shorter. Feb 22 at 17:55

# Python 2, 49 bytes

Prints the sequence indefinitely.

x=c=n=1
while 1:print x;n+=1;c=c*4-c*6/n;x=c-x>>1


Try it online!

Based on the Sage program at the end of the OEIS page.

# Desmos, 46 41 bytes

f(n)=-∑_{k=1}^n(-1)^kknCr(2n-k-1,n-k)/n


A port of the explicit formula but with one-indexing instead of zero-indexing.

Try It On Desmos!

Try It On Desmos! - Prettified

### Proof for the formula:

We start with the explicit formula given in the question: $$F(n)=\frac1{n+1}\sum_{k=0}^n(-1)^k(k+1)\binom{2n-k}{n-k}$$ Then convert it to one-indexing (making a new function $$\f\$$) by doing the following: $$f(n)=F(n-1)=\frac1n\sum_{k=0}^{n-1}(-1)^k(k+1)\binom{2n-k-2}{n-k-1}$$ From there, shift the bounds of the summation up by one, making sure to correct the shift within the summation: $$\frac1n\sum_{k=0}^{n-1}(-1)^k(k+1)\binom{2n-k-2}{n-k-1}=\frac1n\sum_{k=1}^n(-1)^{k-1}k\binom{2n-k-1}{n-k}$$ Factoring out a $$\-1\$$ gives the formula used in my answer: $$f(n)=-\frac1n\sum_{k=1}^n(-1)^kk\binom{2n-k-1}{n-k}$$

# PARI/GP, 36 bytes

n->Vec(2/(1+2*x+sqrt(1-4*x+O(x^n))))


Attempt This Online!

Using the generating function.

# PARI/GP, 39 bytes

n->(matrix(n+1,,i,j,i>abs(j-2))^n)[1,1]


Attempt This Online!

Using this interesting formula on OEIS:

a(n) = the upper left term in M^n, n>0; where M = the infinite square production matrix:
0, 1, 0, 0, 0, 0, ...
1, 1, 1, 0, 0, 0, ...
1, 1, 1, 1, 0, 0, ...
1, 1, 1, 1, 1, 0, ...
1, 1, 1, 1, 1, 1, ...
...
- Gary W. Adamson, Jul 14 2011


# Jelly, 7 bytes

~cŻÄÆmA


This calculates abs(mean(cumsum(choose(-n-1, [0..n])))).

Try it online!

The "negative binomial coefficients" are defined as $$\binom{-a}{b} = (-1)^b \binom{a+b-1}{b}.$$ And they are supported by Jelly's c. So we can rewrite the closed form as:

\begin{align} F_n&=\frac{1}{n+1}\sum_{k=0}^n(-1)^k(k+1)\binom{2n-k}{n-k} \\ & \color{gray}{\text{(introduce negative binomials:)}} \\ &=\frac{1}{n+1}\sum_{k=0}^n(-1)^k(k+1) \color{#0bf}{(-1)^{n-k} \binom{-n-1}{n-k}} \\ & \color{gray}{\text{(factor out powers of -1:)}} \\ &=(-1)^n \frac{1}{n+1} \sum_{k=0}^n (k+1) \binom{-n-1}{n-k} \\ & \color{gray}{\text{(substitute j=n-k:)}} \\ &=(-1)^n \frac{1}{n+1} \sum_{j=0}^n (n+1-j) \binom{-n-1}{j} \end{align}

The ~cŻ generates the negative binomials $$\\binom{-n-1}{0}\$$ through $$\\binom{-n-1}{n}\$$.

Then we use an obscure trick: we can calculate $$\\sum_{j=0}^n (n+1-j) \cdot z_j\$$ as sum(cumsum(z)), or ÄS in Jelly parlance. But then because we want to divide by $$\n+1\$$ immediately after, and our list has $$\n+1\$$ elements, we can write Æm (mean) instead of S (sum).

Here's an example of why this works: \begin{align} & \textrm{sum}(\textrm{cumsum}([a,b,c,d])) \\ =~& (a) + (a+b) + (a+b+c) + (a+b+c+d) \\ =~& 4a+3b+2c+d \end{align}

Finally we still have to multiply by $$\(-1)^n\$$ to fix the sign. But because we know the Fine numbers are never negative, we can just take the absolute value with A.

# Factor + koszul math.combinatorics, 69 bytes

[ 4 dupn + [a,b] [ -1^ -rot nCk * ] with map-index cum-sum mean abs ]


Try it online!

"Mathy" answers cause far too much whitespace in Factor so this is a port of mathcat's Vyxal answer.

# Charcoal, 25 bytes

⊞υ¹≔¹θＦＮ≔⊘⁻↨⊞ＯυΣ×⮌υυ⁰θθＩθ


Attempt This Online! Link is to verbose version of code. Explanation:

⊞υ¹


Start with C(0) = 1.

≔¹θ


Start with F(0) = 1.

ＦＮ


Loop n times.

≔⊘⁻↨⊞ＯυΣ×⮌υυ⁰θθ


Calculate the next Catalan number from the dot product of the list of numbers with its reverse and use that to calculate the next Fine number.

Ｉθ


Output F(n).

# Pyt, 32 bytes

Đ⁺Đř⁻ĐĐ05Ș↔+2ř*⇹ɐ-Á⇹ć⇹⁺*⇹1~⇹^·⇹/


Try it online!

Naive implementation of the formula in the question.

The following walkthrough of the code is worked on an input of n=3

Code Stack Action
Đ 3 3 implicit input; Đuplicate
3 4 increment
Đ 3 4 4 Đuplicate
ř 3 4 [1,2,3,4] řangify
3 4 [0,1,2,3] decrement
ĐĐ 3 4 [0,1,2,3] [0,1,2,3] [0,1,2,3] Đuplicate twice
05Ș 3 0 [0,1,2,3] [0,1,2,3] [0,1,2,3] 4 Push 0, then Șwap the top 5 items on the stack
4 [0,1,2,3] [0,1,2,3] [0,1,2,3] 0 3 Flip the entire stack
+ 4 [0,1,2,3] [0,1,2,3] [0,1,2,3] 3 Remove that pesky 0 by adding
4 [0,1,2,3] [0,1,2,3] [0,1,2,3] 3 [1,2] Push 2 and řangify
* 4 [0,1,2,3] [0,1,2,3] [0,1,2,3] [3,6] Multiply
4 [0,1,2,3] [0,1,2,3] [3,6] [0,1,2,3] Swap the top two items on the stack
ɐ- 4 [0,1,2,3] [0,1,2,3] [[3,2,1,0],[6,5,4,3]] For ɐll pairs of values, subtract
Á 4 [0,1,2,3] [0,1,2,3] [3,2,1,0] [6,5,4,3] Push contents of Árray to stack
4 [0,1,2,3] [0,1,2,3] [6,5,4,3] [3,2,1,0] Swap the top two items on the stack
ć 4 [0,1,2,3] [0,1,2,3] [20,10,4,1] nCr
4 [0,1,2,3] [20,10,4,1] [0,1,2,3] Swap top two items on stack
4 [0,1,2,3] [20,10,4,1] [1,2,3,4] Increment
* 4 [0,1,2,3] [20,20,12,4] multiply element-wise
4 [20,20,12,4] [0,1,2,3] Swap top two items
1~ 4 [20,20,12,4] [0,1,2,3] -1 Push 1, then negate
⇹^ 4 [20,20,12,4] [1,-1,1,-1] Swap top two, then exponentiate
· 4 8 Dot product
⇹/ 2 Swap top two items, then divide; implicit print

# Mathematica, 51 bytes

It's A000957

Use the generating function

$$\sum_{n=0}^\infty F_nz^n=\frac1z\cdot\frac{1-\sqrt{1-4z}}{3-\sqrt{1-4z}}$$

Try it online!

f=SeriesCoefficient[2/(1+Sqrt[1-4*z]+2*z),{z,0,#}]&