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

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

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)

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

Prog

(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

Crossrefs

Cf. A007984, A318407.

Sequence in context: A295723 A306008 A291241 * A365967 A079380 A263402

Adjacent sequences: A318403 A318404 A318405 * A318407 A318408 A318409

Keyword

nonn,easy

Author

Liam Solus, Aug 26 2018

Status

approved