login
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.
3

%I #55 Sep 15 2024 15:21:00

%S 1,0,0,2,2,2,2,6,6,10,10,22,22,42,42,86,86,170,170,342,342,682,682,

%T 1366,1366,2730,2730,5462,5462,10922,10922,21846,21846,43690,43690,

%U 87382,87382,174762,174762,349526,349526,699050,699050,1398102,1398102,2796202

%N 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.

%C 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 :

%C +- ... -+---+- ... -+ +- ... -+---+-+- ... -+

%C | ABC | | XYZ | | ABC | |X| XYZ |

%C +- .. +-+o+-+ .. -+ <--> +- .. +-+-o-+-+ .. -+

%C | ZYX | | CBA | | ZYX |X| | CBA |

%C +- ... -+---+- ... -+ +- ... -+-+---+- ... -+

%C This transformation is reversible, hence a(2*k-1) = a(2*k) for any k>0. - _Paul Tek_, Oct 15 2013

%H Paul Tek, <a href="/A230096/b230096.txt">Table of n, a(n) for n = 0..6646</a>

%H Paul Tek, <a href="/A230096/a230096.png">Illustration of the first terms</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (0,1,0,2).

%F [0 1 1] [1]

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

%F [1 1 0] [0]

%F [0 1 1] [0]

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

%F [1 1 0] [1]

%F 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

%F a(n) = A078008(floor((n+1)/2)). - _Ralf Stephan_, Oct 18 2013

%e A 5 x 1 rectangle can be tiled in 8 ways:

%e +-+-+-+-+-+

%e - |=|=|=|=|=| that shares 5 tiles with its mirrored image,

%e +-+-+-+-+-+

%e +-+-+-+---+

%e - | | |=| | that shares 1 tile with its mirrored image,

%e +-+-+-+---+

%e +-+-+---+-+

%e - |=| | |=| that shares 2 tiles with its mirrored image,

%e +-+-+---+-+

%e +-+---+-+-+

%e - |=| | |=| that shares 2 tiles with its mirrored image,

%e +-+---+-+-+

%e +-+---+---+

%e - | | | | that shares no tile with its mirrored image,

%e +-+---+---+

%e +---+-+-+-+

%e - | |=| | | that shares 1 tile with its mirrored image,

%e +---+-+-+-+

%e +---+-+---+

%e - | = |=| = | that shares 3 tiles with its mirrored image,

%e +---+-+---+

%e +---+---+-+

%e - | | | | that shares no tile with its mirrored image.

%e +---+---+-+

%e Hence, a(5)=2.

%o (PARI) M=[0,1,1;1,0,1;1,1,0];

%o 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]

%o (PARI) Vec(-(2*x^3-x^2+1)/((x^2+1)*(2*x^2-1)) + O(x^100)) \\ _Colin Barker_, Oct 15 2013

%Y Cf. A224918, A225202.

%K nonn,easy

%O 0,4

%A _Paul Tek_, Oct 13 2013