A123347 Number of words of length n over the alphabet {1,2,3,4,5} such that 1 is not followed by an odd letter.

1, 5, 22, 98, 436, 1940, 8632, 38408, 170896, 760400, 3383392, 15054368, 66984256, 298045760, 1326151552, 5900697728, 26255094016, 116821771520, 519797274112, 2312832639488, 10290925106176, 45789365703680, 203739313027072, 906535983515648, 4033622560116736

Offset

0,2

Comments

Appears to be Kekulé numbers for certain benzenoids (see the Cyvin-Gutman book for details).

References

S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 78).

Links

Andrew Howroyd, Table of n, a(n) for n = 0..500

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 17.

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

Formula

From Klaus Brockhaus, Oct 03 2009: (Start)

Inverse binomial transform of A138395.

a(n) = ((2+sqrt(6))^(n+1) + (2-sqrt(6))^(n+1))/4.

a(n) = 4*a(n-1) + 2*a(n-2) for n > 1.

G.f.: (1 + x)/(1 - 4*x - 2*x^2).

(End)

a(n) = A090017(n+1)+A090017(n). - R. J. Mathar, Aug 04 2019

Example

a(2) = 22 because all 25 words of length 2 are included except 11, 13 and 15.

Maple

seq(coeff(series((1+x)/(1-4*x-2*x^2), x, n+1), x, n), n = 0 .. 25); # Muniru A Asiru, Nov 27 2018

Mathematica

LinearRecurrence[{4, 2}, {1, 5}, 30] (* Amiram Eldar, Nov 26 2018 *)

Prog

(PARI) Vec((1 + x)/(1 - 4*x - 2*x^2) + O(x^30)) \\ Andrew Howroyd, Nov 25 2018
(Magma) I:=[1, 5]; [n le 2 select I[n] else 4*Self(n-1) + 2*Self(n-2): n in [1..30]]; // G. C. Greubel, Nov 29 2018
(Sage) s=((1+x)/(1-4*x-2*x^2)).series(x, 50); s.coefficients(x, sparse=False) # G. C. Greubel, Nov 29 2018

Crossrefs

Cf. A138395.

Sequence in context: A129158 A342554 A129164 * A087439 A033452 A346772

Adjacent sequences: A123344 A123345 A123346 * A123348 A123349 A123350

Keyword

nonn,easy

Author

N. J. A. Sloane, Oct 10 2006

Extensions

Edited and new name by Armend Shabani and Andrew Howroyd, Nov 25 2018

Status

approved