A006342 Coloring a circuit with 4 colors.

1, 1, 4, 10, 31, 91, 274, 820, 2461, 7381, 22144, 66430, 199291, 597871, 1793614, 5380840, 16142521, 48427561, 145282684, 435848050, 1307544151, 3922632451, 11767897354, 35303692060, 105911076181, 317733228541, 953199685624, 2859599056870, 8578797170611

Offset: 0

Author

N. J. A. Sloane, Simon Plouffe

Keywords

• nonn
• easy

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

Crossrefs

A214142, A214167

Programs

Magma

[3*3^n/8+1/4+3*(-1)^n/8: n in [0..30]]; // Vincenzo Librandi, Aug 20 2011

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

PARI

Vec((1 - 2*x) / ((1 - x)*(1 + x)*(1 - 3*x)) + O(x^30)) \\ Colin Barker, Nov 07 2017

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

a(n) = a(n-1) + A054878(n-2). - Yuchun Ji, Sep 12 2017

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