A Fine sequence with fine interpretations

Question

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}$$

Task

Standard sequence 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 code-golf; fewest bytes wins.

Answer 1

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 $$

Answer 2

Vyxal, 22 10 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

Answer 3

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.

Answer 4

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!

Answer 5

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?

Answer 6

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}$$

Answer 7

05AB1E, 22 21 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\$.

Try it online or verify all test cases.

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)

---

Original 22 21 bytes answer:

ÝεÈ·<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\$.

Try it online or verify all test cases.

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)

Answer 8

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.

Answer 9

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}$$

Answer 10

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 

Answer 11

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.

Answer 12

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.

Answer 13

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).

Answer 14

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
2ř	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