A125145 a(n) = 3a(n-1) + 3a(n-2). a(0) = 1, a(1) = 4.

1, 4, 15, 57, 216, 819, 3105, 11772, 44631, 169209, 641520, 2432187, 9221121, 34959924, 132543135, 502509177, 1905156936, 7222998339, 27384465825, 103822392492, 393620574951, 1492328902329, 5657848431840, 21450532002507

Offset

0,2

Comments

Number of aa-avoiding words of length n on the alphabet {a,b,c,d}.

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

From Tom Copeland, Nov 08 2014: (Start)

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

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

Joerg Arndt, Matters Computational (The Fxtbook)

D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 7.

Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.

Brian Hopkins and Stéphane Ouvry, Combinatorics of Multicompositions, arXiv:2008.04937 [math.CO], 2020.

Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.

Tanya Khovanova, Recursive Sequences

Index entries for linear recurrences with constant coefficients, signature (3,3).

Formula

G.f.: (1+z)/(1-3z-3z^2). - Emeric Deutsch, Feb 27 2007

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

a(n) = A030195(n)+A030195(n+1) . - R. J. Mathar, Feb 13 2022

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
A125145 := proc(n)
    option remember;
    if n <= 1 then
        op(n+1, [1, 4]) ;
    else
        3*(procname(n-1)+procname(n-2)) ;
    end if;
end proc: # R. J. Mathar, Feb 13 2022

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))
-- Reinhard Zumkeller, Oct 15 2011
(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).

Cf. A128235.

Cf. A180165, A028859, A086347. - Gary W. Adamson, Aug 14 2010

Cf. A002605, A026150, A030195, A080040, A083337, A106435, A108898.

Cf. A000108, A091867, A125145, A104455, A030528, A146559.

Sequence in context: A316592 A077823 A047108 * A242781 A346195 A371854

Adjacent sequences: A125142 A125143 A125144 * A125146 A125147 A125148

Keyword

nonn,easy

Author

Tanya Khovanova, Jan 11 2007

Status

approved