A248880 Number of tilings of an n X 1 rectangle by tiles of dimension 1 X 1 and 2 X 1 such that every tile shares an equal-length edge with a tile of the same size.

1, 0, 1, 1, 2, 1, 4, 3, 7, 7, 13, 14, 24, 28, 45, 56, 86, 111, 165, 218, 317, 426, 611, 831, 1181, 1619, 2286, 3150, 4428, 6123, 8582, 11896, 16641, 23105, 32278, 44865, 62620, 87103, 121499, 169087, 235761, 328214, 457508, 637064, 887857, 1236500, 1723054

Offset: 0

Author

Paul Tek, Mar 05 2015

Keywords

• nonn
• easy

Examples

			A 3 X 1 rectangle can be tiled in three ways:
  +-+-+-+  +-+---+     +---+-+
  | | | |, | |   | and |   | |.
  +-+-+-+  +-+---+     +---+-+
The first tiling is acceptable, as every 1 X 1 tile is next to another 1 X 1 tile (and there are no 2 X 1 tiles).
The second and third tilings are not acceptable, as the 1 X 1 tiles are not next to other 1 X 1 tiles.
Hence, a(3)=1.
		

Links

• Paul Tek, Table of n, a(n) for n = 0..1000
• Paul Tek, Illustration of the formula
• Paul Tek, Illustration of the first terms
• Index entries for linear recurrences with constant coefficients, signature (1,1,-1,0,0,1).

Crossrefs

Cf. A245596.

Programs

PARI

Vec(-(x^2-x+1)*(x^4-x^2+1)/(x^6-x^3+x^2+x-1) + O(x^100)) \\ Colin Barker, Mar 05 2015

Formula

[ 0 1 0 1 0 0 0 ] [1]

[ 0 0 1 0 0 0 0 ] [0]

[ 0 0 1 1 0 0 0 ] [1]

a(n) = [1 0 0 0 0 0 0] * [ 0 0 0 0 1 0 0 ] ^ n * [0], for any n>=0.

[ 0 0 0 0 0 1 0 ] [0]

[ 0 0 0 0 0 0 1 ] [0]

[ 0 1 0 0 0 1 0 ] [1]

G.f.: -(x^2-x+1)*(x^4-x^2+1) / (x^6-x^3+x^2+x-1). - Colin Barker, Mar 05 2015