login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 2
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 (list; graph; refs; listen; history; text; internal format)
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 *)

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 * A079380 A263402 A047082

Adjacent sequences:  A318403 A318404 A318405 * A318407 A318408 A318409

KEYWORD

nonn,easy

AUTHOR

Liam Solus, Aug 26 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 15 11:44 EDT 2021. Contains 345048 sequences. (Running on oeis4.)