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,3

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

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)

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

Prog

(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
(Magma) [Fibonacci(n+1)^3 - 3*Fibonacci(n-1)*Fibonacci(n)^2: n in [1..30]]; // Vincenzo Librandi, Sep 03 2018

Crossrefs

Cf. A000045, A001519.

Sequence in context: A149648 A149649 A149650 * A186364 A105451 A149651

Adjacent sequences: A318373 A318374 A318375 * A318377 A318378 A318379

Keyword

nonn,easy

Author

Liam Solus, Aug 24 2018

Extensions

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

Status

approved