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,4

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

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).

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

Example

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.

Prog

(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

Crossrefs

Cf. A224918, A225202.

Sequence in context: A139554 A366746 A376947 * A116564 A323442 A078014

Adjacent sequences: A230093 A230094 A230095 * A230097 A230098 A230099

Keyword

nonn,easy

Author

Paul Tek, Oct 13 2013

Status

approved