|
|
A125145
|
|
a(n) = 3a(n-1) + 3a(n-2). a(0) = 1, a(1) = 4.
|
|
23
|
|
|
1, 4, 15, 57, 216, 819, 3105, 11772, 44631, 169209, 641520, 2432187, 9221121, 34959924, 132543135, 502509177, 1905156936, 7222998339, 27384465825, 103822392492, 393620574951, 1492328902329, 5657848431840, 21450532002507
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Number of aa-avoiding words of length n on the alphabet {a,b,c,d}.
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.
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).
Ginv(x) = -C[-P(x,3)] = [-1 + sqrt(1+4x/(1+3x))]/2 = x*A104455(-x).
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.)
The inverse of -G(-x) is C[-P(-x,3)]= [1 - sqrt(1-4x/(1-3x))]/2 = x*A104455(x). (End)
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
|
|
LINKS
|
|
|
FORMULA
|
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
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
|
|
MAPLE
|
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
option remember;
if n <= 1 then
op(n+1, [1, 4]) ;
else
3*(procname(n-1)+procname(n-2)) ;
end if;
|
|
MATHEMATICA
|
nn=23; CoefficientList[Series[(1+x)/(1-3x-3x^2), {x, 0, nn}], x] (* Geoffrey Critzer, Feb 09 2014 *)
LinearRecurrence[{3, 3}, {1, 4}, 30] (* Harvey P. Dale, May 01 2022 *)
|
|
PROG
|
(Haskell)
a125145 n = a125145_list !! n
a125145_list =
1 : 4 : map (* 3) (zipWith (+) a125145_list (tail a125145_list))
(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
|
|
CROSSREFS
|
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).
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|