cp's OEIS Frontend

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.

%I A318406 #28 Dec 25 2022 12:15:57
%S A318406 0,1,1,2,3,7,10,22,32,70,102,222,324,704,1028,2232,3260,7076,10336,
%T A318406 22432,32768,71112,103880,225432,329312,714640,1043952,2265472,
%U A318406 3309424,7181744,10491168,22766752,33257920,72172576,105430496,228793312,334223808,725294592,1059518400,2299246592,3358764992
%N 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.
%C A318406 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.
%H A318406 Colin Barker, <a href="/A318406/b318406.txt">Table of n, a(n) for n = 0..1000</a>
%H A318406 A. Radhakrishnan, L. Solus, and C. Uhler. <a href="https://arxiv.org/abs/1706.06091">Counting Markov equivalence classes for DAG models on trees</a>, arXiv:1706.06091 [math.CO], 2017; Discrete Applied Mathematics 244 (2018): 170-185.
%H A318406 <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (0,4,0,-2,0,-2).
%F A318406 From _Colin Barker_, Sep 03 2018: (Start)
%F A318406 G.f.: x*(1 - x)*(1 + x)*(1 + x - x^2) / (1 - 4*x^2 + 2*x^4 + 2*x^6).
%F A318406 a(n) = 4*a(n-2) - 2*a(n-4) - 2*a(n-6) for n>5.
%F A318406 (End)
%t A318406 LinearRecurrence[{0, 4, 0, -2, 0, -2}, {0, 1, 1, 2, 3, 7}, 50] (* _Jean-François Alcover_, Sep 17 2018 *)
%t A318406 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 *)
%o A318406 (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
%o A318406 (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
%Y A318406 Cf. A007984, A318407.
%K A318406 nonn,easy
%O A318406 0,4
%A A318406 _Liam Solus_, Aug 26 2018