OFFSET
0,3
COMMENTS
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
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
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
F. R. Bernhart, Topics in Graph Theory Related to the Five Color Conjecture, Ph.D. Dissertation, Kansas State Univ., 1974.
F. R. Bernhart, Fundamental chromatic numbers, Unpublished. (Annotated scanned copy)
F. R. Bernhart & N. J. A. Sloane, Correspondence, 1977
G. D. Birkhoff, D. C. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60, (1946). 355-451.
Gesualdo Delfino and Jacopo Viti, Potts q-color field theory and scaling random cluster model, arXiv preprint arXiv:1104.4323 [hep-th], 2011.
M. A. Fiol and J. Vilaltella, Some results on the structure of multipoles in the study of snarks, Electron. J. Combin. 22(1) (2015), #P1.45.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Index entries for linear recurrences with constant coefficients, signature (3,1,-3).
FORMULA
G.f.: (1 - 2 x ) / (( 1 - x^2 ) ( 1 - 3 x )).
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
a(n) = 2*a(n-1) + 3*a(n-2) - 1, n > 1. - Gary Detlefs, Jun 21 2010
From Colin Barker, Nov 07 2017: (Start)
a(n) = (3^(n+1) + 5) / 8 for n even.
a(n) = (3^(n+1) - 1) / 8 for n odd.
a(n) = 3*a(n-1) + a(n-2) - 3*a(n-3) for n > 2.
(End)
a(n) = 3*a(n-1) + (3*(-1)^n - 1)/2 for n > 0. - Yuchun Ji, Dec 05 2019
MAPLE
A006342:=-(-1+2*z)/(z-1)/(3*z-1)/(z+1); # conjectured by Simon Plouffe in his 1992 dissertation
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
MATHEMATICA
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 *)
PROG
(Magma) [3*3^n/8+1/4+3*(-1)^n/8: n in [0..30]]; // Vincenzo Librandi, Aug 20 2011
(PARI) Vec((1 - 2*x) / ((1 - x)*(1 + x)*(1 - 3*x)) + O(x^30)) \\ Colin Barker, Nov 07 2017
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
STATUS
approved