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

Author

N. J. A. Sloane, Oct 10 2006

Keywords

• nonn
• easy

Comments

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

Examples

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

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

Crossrefs

Cf. A138395.

Programs

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

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

PARI

Vec((1 + x)/(1 - 4*x - 2*x^2) + O(x^30)) \\ Andrew Howroyd, Nov 25 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

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

Extensions

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