%I M3398 #84 May 27 2024 15:20:19
%S 1,1,4,10,31,91,274,820,2461,7381,22144,66430,199291,597871,1793614,
%T 5380840,16142521,48427561,145282684,435848050,1307544151,3922632451,
%U 11767897354,35303692060,105911076181,317733228541,953199685624,2859599056870,8578797170611
%N Coloring a circuit with 4 colors.
%C Also equal to the number of set partitions of {1,2,...,n+2} with at most 4 parts such that each part does not contain both i,i+1 for 1<=i<n+2 or both 1 and n+2. E.g. a(3)=10 and the set partitions of {1,2,3,4,5} with at most 4 parts with no {i,i+1} or {1,5} in the same part are {14|25|3}, {13|25|4}, {14|2|35}, {1|24|35}, {13|24|5}, {1|25|3|4}, {1|2|35|4}, {14|2|3|5}, {1|24|3|5}, {13|2|4|5}. - _Mike Zabrocki_, Sep 08 2020
%C Also a(n) equals the number of color-complete multipoles with n terminals (that is, having all the states allowed by the Parity Lemma). - _Miquel A. Fiol_, May 27 2024
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Vincenzo Librandi, <a href="/A006342/b006342.txt">Table of n, a(n) for n = 0..1000</a>
%H F. R. Bernhart, <a href="https://www.researchgate.net/publication/303755782_Topics_in_Graph_Theory_Related_to_the_Five_Color_Conjecture">Topics in Graph Theory Related to the Five Color Conjecture</a>, Ph.D. Dissertation, Kansas State Univ., 1974.
%H F. R. Bernhart, <a href="/A000296/a000296_1.pdf">Fundamental chromatic numbers</a>, Unpublished. (Annotated scanned copy)
%H F. R. Bernhart & N. J. A. Sloane, <a href="/A001683/a001683.pdf">Correspondence, 1977</a>
%H G. D. Birkhoff, D. C. Lewis, <a href="https://doi.org/10.1090/S0002-9947-1946-0018401-4">Chromatic polynomials</a>, Trans. Amer. Math. Soc. 60, (1946). 355-451.
%H Gesualdo Delfino and Jacopo Viti, <a href="http://arxiv.org/abs/1104.4323">Potts q-color field theory and scaling random cluster model</a>, arXiv preprint arXiv:1104.4323 [hep-th], 2011.
%H M. A. Fiol and J. Vilaltella, <a href="https://doi.org/10.37236/3629">Some results on the structure of multipoles in the study of snarks</a>, Electron. J. Combin. 22(1) (2015), #P1.45.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,1,-3).
%F G.f.: (1 - 2 x ) / (( 1 - x^2 ) ( 1 - 3 x )).
%F Binomial transform of A002001 (with interpolated zeros). Partial sums of A054878. E.g.f.: exp(x)(3*cosh(2*x) + 1)/4; a(n) = 3*3^n/8 + 1/4 + 3(-1)^n/8 = Sum_{k=0..n} (3^k + 3(-1)^k)/4. - _Paul Barry_, Sep 03 2003
%F a(n) = 2*a(n-1) + 3*a(n-2) - 1, n > 1. - _Gary Detlefs_, Jun 21 2010
%F a(n) = a(n-1) + A054878(n-2). - _Yuchun Ji_, Sep 12 2017
%F From _Colin Barker_, Nov 07 2017: (Start)
%F a(n) = (3^(n+1) + 5) / 8 for n even.
%F a(n) = (3^(n+1) - 1) / 8 for n odd.
%F a(n) = 3*a(n-1) + a(n-2) - 3*a(n-3) for n > 2.
%F (End)
%F a(n) = 3*a(n-1) + (3*(-1)^n - 1)/2 for n > 0. - _Yuchun Ji_, Dec 05 2019
%p A006342:=-(-1+2*z)/(z-1)/(3*z-1)/(z+1); # conjectured by _Simon Plouffe_ in his 1992 dissertation
%p a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=2*a[n-1]+3*a[n-2]-1 od: seq(a[n], n=1..26); # _Zerinvary Lajos_, Apr 28 2008
%t CoefficientList[Series[(1-2 x)/((1-x^2) (1-3 x)),{x,0,30}],x] (* or *) LinearRecurrence[{3,1,-3},{1,1,4},30] (* _Harvey P. Dale_, Aug 16 2016 *)
%o (Magma) [3*3^n/8+1/4+3*(-1)^n/8: n in [0..30]]; // _Vincenzo Librandi_, Aug 20 2011
%o (PARI) Vec((1 - 2*x) / ((1 - x)*(1 + x)*(1 - 3*x)) + O(x^30)) \\ _Colin Barker_, Nov 07 2017
%Y A214142, A214167
%K nonn,easy
%O 0,3
%A _N. J. A. Sloane_, _Simon Plouffe_