A123620 Expansion of (1 + x + x^2) / (1 - 3*x - 3*x^2).

1, 4, 16, 60, 228, 864, 3276, 12420, 47088, 178524, 676836, 2566080, 9728748, 36884484, 139839696, 530172540, 2010036708, 7620627744, 28891993356, 109537863300, 415289569968, 1574482299804, 5969315609316, 22631393727360, 85802128010028, 325300565212164

Offset: 0

Author

N. J. A. Sloane, Nov 20 2006

Keywords

• nonn
• easy

Comments

From Johannes W. Meijer, Aug 14 2010: (Start)

A berserker sequence, see A180141. For the corner squares 16 A[5] vectors with decimal values between 3 and 384 lead to this sequence. These vectors lead for the side squares to A180142 and for the central square to A155116.

This sequence belongs to a family of sequences with GF(x) = (1+x+k*x^2)/(1-3*x+(k-4)*x^2). Berserker sequences that are members of this family are 4*A055099(n) (k=2; with leading 1 added), A123620 (k=1; this sequence), A000302 (k=0), 4*A179606 (k=-1; with leading 1 added) and A180141 (k=-2). Some other members of this family are 4*A003688 (k=3; with leading 1 added), 4*A003946 (k=4; with leading 1 added), 4*A002878 (k=5; with leading 1 added) and 4*A033484 (k=6; with leading 1 added).

(End)

a(n) is the number of length n sequences on an alphabet of 4 letters that do not contain more than 2 consecutive equal letters. For example, a(3)=60 because we count all 4^3=64 words except: aaa, bbb, ccc, ddd. - Geoffrey Critzer, Mar 12 2014

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• A. Burstein and T. Mansour, Words restricted by 3-letter generalized multipermutation patterns, arXiv:math/0112281 [math.CO], 2001.
• A. Burstein and T. Mansour, Words restricted by 3-letter generalized multipermutation patterns, Annals. Combin., 7 (2003), 1-14.
• Martin Burtscher, Igor Szczyrba, Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
• P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 205
• Index entries for linear recurrences with constant coefficients, signature (3,3).

Crossrefs

Column 4 in A265584.

Programs

Magma

[1] cat [Round(((2^(1-n)*(-(3-Sqrt(21))^(1+n) + (3+Sqrt(21))^(1+n))))/(3*Sqrt(21))): n in [1..50]]; // G. C. Greubel, Oct 26 2017

Mathematica

nn=25;CoefficientList[Series[(1-z^(m+1))/(1-r z +(r-1)z^(m+1))/.{r->4,m->2},{z,0,nn}],z] (* Geoffrey Critzer, Mar 12 2014 *)
CoefficientList[Series[(1 + x + x^2)/(1 - 3 x - 3 x^2), {x, 0, 40}], x] (* Vincenzo Librandi, Mar 14 2014 *)
LinearRecurrence[{3,3},{1,4,16},30] (* Harvey P. Dale, Jul 14 2023 *)

PARI

my(x='x+O('x^50)); Vec((1+x+x^2)/(1-3*x-3*x^2)) \\ G. C. Greubel, Oct 16 2017

Formula

a(0)=1, a(1)=4, a(2)=16, a(n)=3*a(n-1)+3*a(n-2) for n>2. - Philippe Deléham, Sep 18 2009

a(n) = ((2^(1-n)*(-(3-sqrt(21))^(1+n) + (3+sqrt(21))^(1+n)))) / (3*sqrt(21)) for n>0. - Colin Barker, Oct 17 2017