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
Examples
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.
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).
Crossrefs
Cf. A230096.
Programs
-
PARI
Vec(-(x^6+x^3+1)/((x^2+x+1)*(x^4+x-1)) + O(x^100)) \\ Colin Barker, Jul 28 2014
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