A230096 Number of tilings of an n X 1 rectangle (using tiles of dimension 1 X 1 and 2 X 1) that share no tile at the same position with their mirrored image.

1, 0, 0, 2, 2, 2, 2, 6, 6, 10, 10, 22, 22, 42, 42, 86, 86, 170, 170, 342, 342, 682, 682, 1366, 1366, 2730, 2730, 5462, 5462, 10922, 10922, 21846, 21846, 43690, 43690, 87382, 87382, 174762, 174762, 349526, 349526, 699050, 699050, 1398102, 1398102, 2796202

Offset: 0

Author

Paul Tek, Oct 13 2013

Keywords

• nonn
• easy

Comments

For any k>0, it is possible to transform a pair of symmetric tilings of length 2*k-1 that share no tile with their mirrored image into a pair of symmetric tilings of length 2*k with the same property by inserting a 1 X 1 tile next to the central 2 X 1 tile :

+- ... -+---+- ... -+ +- ... -+---+-+- ... -+

| ABC | | XYZ | | ABC | |X| XYZ |

+- .. +-+o+-+ .. -+ <--> +- .. +-+-o-+-+ .. -+

| ZYX | | CBA | | ZYX |X| | CBA |

+- ... -+---+- ... -+ +- ... -+-+---+- ... -+

This transformation is reversible, hence a(2*k-1) = a(2*k) for any k>0. - Paul Tek, Oct 15 2013

Examples

			A 5 x 1 rectangle can be tiled in 8 ways:
  +-+-+-+-+-+
- |=|=|=|=|=| that shares 5 tiles with its mirrored image,
  +-+-+-+-+-+
  +-+-+-+---+
- | | |=|   | that shares 1 tile with its mirrored image,
  +-+-+-+---+
  +-+-+---+-+
- |=| |   |=| that shares 2 tiles with its mirrored image,
  +-+-+---+-+
  +-+---+-+-+
- |=|   | |=| that shares 2 tiles with its mirrored image,
  +-+---+-+-+
  +-+---+---+
- | |   |   | that shares no tile with its mirrored image,
  +-+---+---+
  +---+-+-+-+
- |   |=| | | that shares 1 tile with its mirrored image,
  +---+-+-+-+
  +---+-+---+
- | = |=| = | that shares 3 tiles with its mirrored image,
  +---+-+---+
  +---+---+-+
- |   |   | | that shares no tile with its mirrored image.
  +---+---+-+
Hence, a(5)=2.
		

Links

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

Crossrefs

Cf. A224918, A225202.

Programs

PARI

M=[0,1,1;1,0,1;1,1,0];
a(n)=if(n%2==0, [1,0,0]*M^(n/2)*[1;0;0], [1,0,0]*M^((n-1)/2)*[0;1;1])[1]

PARI

Vec(-(2*x^3-x^2+1)/((x^2+1)*(2*x^2-1)) + O(x^100)) \\ Colin Barker, Oct 15 2013

Formula

[0 1 1] [1]

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

[1 1 0] [0]

[0 1 1] [0]

a(2*k-1) = [1 0 0] * [1 0 1]^k * [1], for any k>=1.

[1 1 0] [1]

a(n) = a(n-2)+2*a(n-4). G.f.: -(2*x^3-x^2+1) / ((x^2+1)*(2*x^2-1)). - Colin Barker, Oct 14 2013

a(n) = A078008(floor((n+1)/2)). - Ralf Stephan, Oct 18 2013