A089928 a(n) = 2*a(n-1) + 2*a(n-3) + a(n-4), with a(0)=1, a(1)=2, a(3)=4, a(4)=10.

1, 2, 4, 10, 25, 60, 144, 348, 841, 2030, 4900, 11830, 28561, 68952, 166464, 401880, 970225, 2342330, 5654884, 13652098, 32959081, 79570260, 192099600, 463769460, 1119638521, 2703046502, 6525731524, 15754509550, 38034750625, 91824010800

Offset

0,2

Comments

a(n) is the number of tilings of an n-board (a board of size n X 1) using white squares, black squares, and white (1,1)-fences. A (1,1)-fence is a tile composed of two squares separated by a gap of width 1. - Michael A. Allen, Mar 12 2021

a(n) is the number of tilings of an n-board using white squares, black squares, white trominoes, black trominoes, and white tetrominoes. - Michael A. Allen, Mar 12 2021

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Kenneth Edwards and Michael A. Allen, New combinatorial interpretations of the Fibonacci numbers squared, golden rectangle numbers, and Jacobsthal numbers using two types of tile, J. Int. Seq. 24 (2021) Article 21.3.8.

Andreas M. Hinz and Paul K. Stockmeyer, Precious Metal Sequences and Sierpinski-Type Graphs, J. Integer Seq., Vol 25 (2022), Article 22.4.8.

Index entries for sequences related to Chebyshev polynomials.

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

Formula

a(n) = ( (1+sqrt(2))^(n+2) + (1-sqrt(2))^(n+2) + 2*(-1)^floor(n/2) )/8.

a(n) = (-i)^n*Sum_{k=0..floor(n/2)} U(n-2*k, i) with i^2 = -1.

a(n) + a(n+2) = A000129(n+3). - Alex Ratushnyak, Aug 06 2012

G.f.: 1/ ( (1+2*x)*(1-2*x-x^2) ). - R. J. Mathar, Apr 26 2013

4*a(n) = A057077(n) + A001333(n+2). - R. J. Mathar, Apr 26 2013

a(2*n) = (A000129(n+1))^2 = A079291(n+1). - Michael A. Allen, Mar 12 2021

a(2*n+1) = A000129(n+1)*A000129(n+2) = A114620(n+1). - Michael A. Allen, Mar 12 2021

Mathematica

CoefficientList[Series[1/(1-2x-2x^3-x^4), {x, 0, 30}], x] (* Michael A. Allen, Mar 12 2021 *)
LinearRecurrence[{2, 0, 2, 1}, {1, 2, 4, 10}, 41] (* G. C. Greubel, Aug 18 2022 *)
nxt[{a_, b_, c_, d_}]:={b, c, d, 2d+2b+a}; NestList[nxt, {1, 2, 4, 10}, 30][[;; , 1]] (* Harvey P. Dale, Jul 18 2024 *)

Prog

(Magma) [(Evaluate(DicksonFirst(n+2, -1), 2) + 2*(-1)^Binomial(n, 2))/8: n in [0..40]]; // G. C. Greubel, Aug 18 2022
(SageMath) [(lucas_number2(n+2, 2, -1) +2*(-1)^binomial(n, 2))/8 for n in (0..40)] # G. C. Greubel, Aug 18 2022

Crossrefs

Cf. A000129, A001333, A006498, A057077, A079291, A114620.

Sequence in context: A148091 A123420 A000458 * A173610 A036887 A307578

Adjacent sequences: A089925 A089926 A089927 * A089929 A089930 A089931

Keyword

easy,nonn

Author

Paul Barry, Nov 15 2003

Extensions

Formula corrected by Max Alekseyev, Aug 22 2013

Status

approved