|
%I #78 Oct 13 2022 02:51:39
%S 1,4,15,57,216,819,3105,11772,44631,169209,641520,2432187,9221121,
%T 34959924,132543135,502509177,1905156936,7222998339,27384465825,
%U 103822392492,393620574951,1492328902329,5657848431840,21450532002507
%N a(n) = 3a(n-1) + 3a(n-2). a(0) = 1, a(1) = 4.
%C Number of aa-avoiding words of length n on the alphabet {a,b,c,d}.
%C Equals row 3 of the array shown in A180165, the INVERT transform of A028859 and the INVERTi transform of A086347. - _Gary W. Adamson_, Aug 14 2010
%C From _Tom Copeland_, Nov 08 2014: (Start)
%C This array is one of a family related by compositions of C(x)= [1-sqrt(1-4x)]/2, an o.g.f. for A000108; its inverse Cinv(x) = x(1-x); and the special Mobius transformation P(x,t) = x / (1+t*x) with inverse P(x,-t) in x. Cf. A091867.
%C O.g.f.: G(x) = P[P[P[-Cinv(-x),-1],-1],-1] = P[-Cinv(-x),-3] = x*(1+x)/[1-3x(1-x)]= x*A125145(x).
%C Ginv(x) = -C[-P(x,3)] = [-1 + sqrt(1+4x/(1+3x))]/2 = x*A104455(-x).
%C G(-x) = -x(1-x) * [ 1 - 3*[x*(1+x)] + 3^2*[x*(1+x)]^2 - ...] , and so this array is related to finite differences in the row sums of A030528 * Diag((-3)^1,3^2,(-3)^3,..). (Cf. A146559.)
%C The inverse of -G(-x) is C[-P(-x,3)]= [1 - sqrt(1-4x/(1-3x))]/2 = x*A104455(x). (End)
%C Number of 3-compositions of n+1 restricted to parts 1 and 2 (and allowed zeros); see Hopkins & Ouvry reference. - _Brian Hopkins_, Aug 16 2020
%H Reinhard Zumkeller, <a href="/A125145/b125145.txt">Table of n, a(n) for n = 0..1000</a>
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>
%H D. Birmajer, J. B. Gil, and M. D. Weiner, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Gil/gil6.html">On the Enumeration of Restricted Words over a Finite Alphabet</a>, J. Int. Seq. 19 (2016) # 16.1.3, Example 7.
%H Martin Burtscher, Igor Szczyrba, and 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 Brian Hopkins and Stéphane Ouvry, <a href="https://arxiv.org/abs/2008.04937">Combinatorics of Multicompositions</a>, arXiv:2008.04937 [math.CO], 2020.
%H Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Janjic/janjic63.html">On Linear Recurrence Equations Arising from Compositions of Positive Integers</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (3,3).
%F G.f.: (1+z)/(1-3z-3z^2). - _Emeric Deutsch_, Feb 27 2007
%F a(n) = (5*sqrt(21)/42 + 1/2)*(3/2 + sqrt(21)/2))^(n-1) + (-5*sqrt(21)/42 + 1/2)*(3/2 - sqrt(21)/2))^(n-1). - _Antonio Alberto Olivares_, Mar 20 2008
%F a(n) = A030195(n)+A030195(n+1) . - _R. J. Mathar_, Feb 13 2022
%F E.g.f.: exp(3*x/2)*(21*cosh(sqrt(21)*x/2) + 5*sqrt(21)*sinh(sqrt(21)*x/2))/21. - _Stefano Spezia_, Aug 04 2022
%p a[0]:=1: a[1]:=4: for n from 2 to 27 do a[n]:=3*a[n-1]+3*a[n-2] od: seq(a[n],n=0..27); # _Emeric Deutsch_, Feb 27 2007
%p A125145 := proc(n)
%p option remember;
%p if n <= 1 then
%p op(n+1,[1,4]) ;
%p else
%p 3*(procname(n-1)+procname(n-2)) ;
%p end if;
%p end proc: # _R. J. Mathar_, Feb 13 2022
%t nn=23;CoefficientList[Series[(1+x)/(1-3x-3x^2),{x,0,nn}],x] (* _Geoffrey Critzer_, Feb 09 2014 *)
%t LinearRecurrence[{3,3},{1,4},30] (* _Harvey P. Dale_, May 01 2022 *)
%o (Haskell)
%o a125145 n = a125145_list !! n
%o a125145_list =
%o 1 : 4 : map (* 3) (zipWith (+) a125145_list (tail a125145_list))
%o -- _Reinhard Zumkeller_, Oct 15 2011
%o (Magma) I:=[1,4]; [n le 2 select I[n] else 3*Self(n-1)+3*Self(n-2): n in [1..40]]; // _Vincenzo Librandi_, Nov 10 2014
%Y Cf. A028859 = a(n+2) = 2 a(n+1) + 2 a(n); A086347 = On a 3 X 3 board, number of n-move routes of chess king ending at a given side cell. a(n) = 4a(n-1) + 4a(n-2).
%Y Cf. A128235.
%Y Cf. A180165, A028859, A086347. - _Gary W. Adamson_, Aug 14 2010
%Y Cf. A002605, A026150, A030195, A080040, A083337, A106435, A108898.
%Y Cf. A000108, A091867, A125145, A104455, A030528, A146559.
%K nonn,easy
%O 0,2
%A _Tanya Khovanova_, Jan 11 2007
| 