A006342 Coloring a circuit with 4 colors. (Formerly M3398)

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,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

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.

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

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

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

A214142, A214167

Sequence in context: A034730 A321143 A095127 * A258041 A289447 A135831

Adjacent sequences: A006339 A006340 A006341 * A006343 A006344 A006345

Keyword

nonn,easy

Author

N. J. A. Sloane, Simon Plouffe

Status

approved