A127864 Number of tilings of a 2 X n board with 1 X 1 and L-shaped tiles (where the L-shaped tiles cover 3 squares).

1, 1, 5, 11, 33, 87, 241, 655, 1793, 4895, 13377, 36543, 99841, 272767, 745217, 2035967, 5562369, 15196671, 41518081, 113429503, 309895169, 846649343, 2313089025, 6319476735, 17265131521, 47169216511, 128868696065, 352075825151, 961889042433, 2627929735167

Offset: 0

Author

Silvia Heubach (sheubac(AT)calstatela.edu), Feb 03 2007

Keywords

• easy
• nonn

Comments

The signed version of this sequence appears as A077917.

Examples

			a(2) = 5 because the 2 X 2 board can be tiled either with 4 squares or with a single L-shaped tile (in four orientations) together with a single square tile.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• P. Z. Chinn, R. Grimaldi and S. Heubach, Tiling with Ls and Squares, J. Int. Sequences 10 (2007) #07.2.8.
• S. Heubach, Tiling with Ls and Squares, 2005.
• Index entries for linear recurrences with constant coefficients, signature (1,4,2).

Crossrefs

Cf. A077917, A127865, A127866, A127867, A127868, A127869, A127870, A127871, A127872.

Column k=2 of A220054. - Alois P. Heinz, Dec 03 2012

Programs

Magma

I:=[1,1,5]; [n le 3 select I[n] else Self(n-1) + 4*Self(n-2) + 2*Self(n-3): n in [1..41]]; // G. C. Greubel, Dec 08 2022

Mathematica

CoefficientList[Series[1/(1-x-4*x^2-2*x^3), {x,0,30}], x]

SageMath

A028860 = BinaryRecurrenceSequence(2,2,-1,1)
def A127864(n): return A028860(n+2) + (-1)^n
[A127864(n) for n in range(51)] # G. C. Greubel, Dec 08 2022

Formula

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

a(n) = (-1)^n + (1/sqrt(3)) * ((1+sqrt(3))^n - (1-sqrt(3))^n).

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

a(n) = A028860(n+2) + (-1)^n. - R. J. Mathar, Oct 29 2010

E.g.f.: exp(-x) + (2/sqrt(3))*exp(x)*sinh(sqrt(3)*x). - G. C. Greubel, Dec 08 2022

From Greg Dresden, Nov 10 2024: (Start)

a(n) = 1 + 4*a(n-2) + 6*Sum_{i=0..n-3} a(i) for n>1.

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