%I #57 Sep 16 2024 23:59:21
%S 1,4,16,60,228,864,3276,12420,47088,178524,676836,2566080,9728748,
%T 36884484,139839696,530172540,2010036708,7620627744,28891993356,
%U 109537863300,415289569968,1574482299804,5969315609316,22631393727360,85802128010028,325300565212164
%N Expansion of (1 + x + x^2) / (1 - 3*x - 3*x^2).
%C From _Johannes W. Meijer_, Aug 14 2010: (Start)
%C 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.
%C 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).
%C (End)
%C 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
%H Vincenzo Librandi, <a href="/A123620/b123620.txt">Table of n, a(n) for n = 0..1000</a>
%H A. Burstein and T. Mansour, <a href="https://arxiv.org/abs/math/0112281">Words restricted by 3-letter generalized multipermutation patterns</a>, arXiv:math/0112281 [math.CO], 2001.
%H A. Burstein and T. Mansour, <a href="http://dx.doi.org/10.1007/s000260300000">Words restricted by 3-letter generalized multipermutation patterns</a>, Annals. Combin., 7 (2003), 1-14.
%H Martin Burtscher, Igor Szczyrba, Rafał Szczyrba, <a href="http://www.emis.de/journals/JIS/VOL18/Szczyrba/sz3.html">Analytic Representations of the n-anacci Constants and Generalizations Thereof</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 205
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (3,3).
%F 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
%F 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
%t 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 *)
%t CoefficientList[Series[(1 + x + x^2)/(1 - 3 x - 3 x^2), {x, 0, 40}], x] (* _Vincenzo Librandi_, Mar 14 2014 *)
%t LinearRecurrence[{3,3},{1,4,16},30] (* _Harvey P. Dale_, Jul 14 2023 *)
%o (PARI) my(x='x+O('x^50)); Vec((1+x+x^2)/(1-3*x-3*x^2)) \\ _G. C. Greubel_, Oct 16 2017
%o (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
%Y Column 4 in A265584.
%K nonn,easy
%O 0,2
%A _N. J. A. Sloane_, Nov 20 2006