A245596 Number of tilings of an n X 1 rectangle by tiles of dimension 1 X 1 and 2 X 1 such that every tile is next to a tile of different size.

1, 0, 0, 2, 1, 1, 4, 3, 4, 8, 9, 12, 19, 24, 33, 48, 64, 88, 124, 169, 233, 324, 445, 614, 850, 1171, 1616, 2233, 3080, 4251, 5870, 8100, 11180, 15434, 21301, 29401, 40584, 56015, 77316, 106720, 147301, 203316, 280635, 387352, 534653

Offset

0,4

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 (0,0,1,1,1,1).

Formula

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

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

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

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

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

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

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

G.f.: (x^6+x^3+1)/(-x^6-x^5-x^4-x^3+1) = -(x^6+x^3+1)/((x^2+x+1)*(x^4+x-1)). - Colin Barker, Jul 27 2014

a(n) = a(n-3)+a(n-4)+a(n-5)+a(n-6) for n>6. - Colin Barker, Jul 28 2014

Example

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

Prog

(PARI) Vec(-(x^6+x^3+1)/((x^2+x+1)*(x^4+x-1)) + O(x^100)) \\ Colin Barker, Jul 28 2014

Crossrefs

Cf. A230096.

Sequence in context: A240769 A357320 A174455 * A326611 A083293 A350912

Adjacent sequences: A245593 A245594 A245595 * A245597 A245598 A245599

Keyword

nonn,easy

Author

Paul Tek, Jul 27 2014

Status

approved