A316726 The number of ways to tile (with squares and rectangles) a 2 X (n+2) strip with the upper left and upper right squares removed.

2, 4, 15, 46, 150, 480, 1545, 4964, 15958, 51292, 164871, 529946, 1703418, 5475328, 17599457, 56570280, 181834970, 584475732, 1878691887, 6038716422, 19410365422, 62391120800, 200545011401, 644615789580, 2072001259342, 6660074556204, 21407609138375

Offset: 0

Author

Zijing Wu, Jul 11 2018

Keywords

• nonn
• easy

Comments

Each number in the sequence is the partial sum of A033505 (n starts at 0, each number add one if n is even). We can also find the recursion relation a(n) = 2*a(n-1) + 4*a(n-2) - a(n-4) for the sequence, which can be proved by induction.

Examples

			For n=4, a(4) = 150 = 2*a(3) + 4*a(2) - a(0).
		

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (2,4,0,-1).

Crossrefs

Cf. A033505, A030186.

Programs

Mathematica

CoefficientList[ Series[(-x^2 + 1)/(x^4 - 4x^2 - 2x + 1), {x, 0, 27}], x] (* or *) LinearRecurrence[{2, 4, 0, -1}, {2, 4, 15, 46}, 27] (* Robert G. Wilson v, Jul 15 2018 *)

PARI

Vec((2 - x^2) / ((1 + x)*(1 - 3*x - x^2 + x^3)) + O(x^30)) \\ Colin Barker, Jul 12 2018

Formula

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

G.f.: (2 - x^2) / ((1 + x)*(1 - 3*x - x^2 + x^3)). - Colin Barker, Jul 12 2018

a(n) = A030186(n) + 2*A033505(n-1) + a(n-2). - Greg Dresden and Ge Ma, Jul 12 2025

Extensions

More terms from Colin Barker, Jul 12 2018