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

Author

Paul Barry, Nov 15 2003

Keywords

• easy
• nonn

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

Crossrefs

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

Programs

Magma

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

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

SageMath

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

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

Extensions

Formula corrected by Max Alekseyev, Aug 22 2013