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

Author

Tanya Khovanova, Jan 11 2007

Keywords

• nonn
• easy

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
• Jean-Paul Allouche, Jeffrey Shallit, and Manon Stipulanti, Combinatorics on words and generating Dirichlet series of automatic sequences, arXiv:2401.13524 [math.CO], 2025. See p. 14.
• 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).

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.

Programs

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

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 *)

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 + (-5*sqrt(21)/42 + 1/2)*(3/2 - sqrt(21)/2)^n. - 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

a(n) = (((3 + sqrt(21)) / 2)^(n+2) - ((3 - sqrt(21)) / 2)^(n+2)) / (3 * sqrt(21)). - Werner Schulte, Dec 17 2024