A318406 For n > 4, a(n) = a(n-1) + a(n-2) if n is even and a(n) = 3*a(n-2) + a(n-4) - a(n-5) if n is odd; a(0) = 0, a(1) = 1, a(2) = 1, a(3) = 2, and a(4) = 3.

0, 1, 1, 2, 3, 7, 10, 22, 32, 70, 102, 222, 324, 704, 1028, 2232, 3260, 7076, 10336, 22432, 32768, 71112, 103880, 225432, 329312, 714640, 1043952, 2265472, 3309424, 7181744, 10491168, 22766752, 33257920, 72172576, 105430496, 228793312, 334223808, 725294592, 1059518400, 2299246592, 3358764992

Offset: 0

Author

Liam Solus, Aug 26 2018

Keywords

• nonn
• easy

Comments

a(n) is the number of Markov equivalence classes whose skeleton is the caterpillar graph on n nodes. See Corollary 4.4 in the paper by A. Radhakrishnan et al. below.

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 (0,4,0,-2,0,-2).

Crossrefs

Cf. A007984, A318407.

Programs

Mathematica

LinearRecurrence[{0, 4, 0, -2, 0, -2}, {0, 1, 1, 2, 3, 7}, 50] (* Jean-François Alcover, Sep 17 2018 *)
nxt[{n_,a_,b_,c_,d_,e_}]:={n+1,b,c,d,e,If[OddQ[n],d+e,3d-a+b]}; NestList[nxt,{4,0,1,1,2,3},40][[All,2]] (* Harvey P. Dale, Dec 25 2022 *)

PARI

a(n) = if (n > 4, if (n%2, 3*a(n-2) + a(n-4) - a(n-5), a(n-1) + a(n-2)), if (n > 1, n-1, n)); \\ Michel Marcus, Sep 03 2018

PARI

concat(0, Vec(x*(1 - x)*(1 + x)*(1 + x - x^2) / (1 - 4*x^2 + 2*x^4 + 2*x^6) + O(x^40))) \\ Colin Barker, Sep 03 2018

Formula

From Colin Barker, Sep 03 2018: (Start)

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

a(n) = 4*a(n-2) - 2*a(n-4) - 2*a(n-6) for n>5.

(End)