A318376 a(n) = F(n+1)^3 - 3*F(n-1)*F(n)^2, where F(n) = A000045(n), the n-th Fibonacci number.

1, 1, 5, 15, 71, 287, 1237, 5205, 22105, 93547, 396419, 1679019, 7112825, 30129785, 127632829, 540659703, 2290273903, 9701751655, 41097286445, 174090887853, 737460853361, 3123934276211, 13233197998795, 56056726205715, 237460102927921, 1005897137745457, 4261048654187957

Offset: 0

Author

Liam Solus, Aug 24 2018

Keywords

• nonn
• easy

Comments

a(n) is the number of Markov equivalence classes whose skeleton is a spider graph with three legs, each of which contains n nodes of degree at most two.

A001519 admits the related formula A001519(n) = F(n+1)^2 - 2*F(n-1)*F(n).

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• A. Radhakrishnan, L. Solus, and C. Uhler. Counting Markov equivalence classes for DAG models on trees, arXiv:1706.06091 [math.CO], 2017; Discrete Applied Mathematics 244 (2018): 170-185.
• Index entries for linear recurrences with constant coefficients, signature (3,6,-3,-1).

Crossrefs

Cf. A000045, A001519.

Programs

Magma

[Fibonacci(n+1)^3 - 3*Fibonacci(n-1)*Fibonacci(n)^2: n in [1..30]]; // Vincenzo Librandi, Sep 03 2018

Mathematica

CoefficientList[Series[(1 - 2 x - 4 x^2 - 3 x^3) / ((1 + x - x^2) (1-4 x-x^2)), {x, 0, 26}], x] (* Michael De Vlieger, Aug 25 2018 *)
LinearRecurrence[{3, 6, -3, -1}, {1, 1, 5, 15, 71}, 26] (* Stefano Spezia, Sep 02 2018; a(0)=1 amended by Georg Fischer, Apr 03 2019 *)
Table[Fibonacci[n + 1]^3 - 3 Fibonacci[n-1] Fibonacci[n]^2, {n, 0, 25}] (* Vincenzo Librandi, Sep 03 2018 *)
#[[3]]^3-3#[[1]]#[[2]]^2&/@Partition[Fibonacci[Range[-1,30]],3,1] (* Harvey P. Dale, Sep 02 2023 *)

PARI

a(n) = fibonacci(n+1)^3 - 3*fibonacci(n-1)*fibonacci(n)^2; \\ Michel Marcus, Aug 25 2018

PARI

my(x='x+O('x^31));  Vec((1 - 2*x - 4*x^2 - 3*x^3) / ((1 + x - x^2)*(1 - 4*x - x^2))) \\ Colin Barker, Aug 25 2018 and Sep 06 2018

Formula

From Colin Barker, Aug 25 2018: (Start)

G.f.: (1 - 2 x - 4 x^2 - 3 x^3) / ((1 + x - x^2)*(1 - 4*x - x^2)).

a(n) = 3*a(n-1) + 6*a(n-2) - 3*a(n-3) - a(n-4) for n>3.

(End)

Extensions

a(0) = 1 inserted by Vincenzo Librandi, Sep 03 2018