login
Number of tilings of an n X 1 rectangle (using tiles of dimension 1 X 1 and 2 X 1) that are not the concatenation of smaller equally-sized tilings.
2

%I #27 May 06 2013 13:22:22

%S 1,1,2,1,7,0,20,9,28,9,143,39,376,105,340,441,2583,480,6764,2400,7235,

%T 6897,46367,10332,88625,50193,151436,126504,832039,127431,2178308,

%U 974169,2618488,2484873,9209899,3202560,39088168,17218617,47865787,33738201,267914295,49047180,701408732,303913896,624579100

%N Number of tilings of an n X 1 rectangle (using tiles of dimension 1 X 1 and 2 X 1) that are not the concatenation of smaller equally-sized tilings.

%C a(p)+1 = Fibonacci(p+1) for any prime p.

%C a(2^k) = Fibonacci(2^(k-1))^2 for k>0.

%C a(n) <= A225202(n).

%H Paul Tek, <a href="/A224918/b224918.txt">Table of n, a(n) for n = 1..1000</a>

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

%H Paul Tek, <a href="/A224918/a224918.txt">PERL program for this sequence</a>

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

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

%e - | | | | | that is the concatenation of | |, | |, | | and | |

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

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

%e - | | | | that is the concatenation of | | and | | |

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

%e +-+---+-+

%e - | | | | that is not the concatenation of smaller equally sized tilings,

%e +-+---+-+

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

%e - | | | | that is the concatenation of | | | and | |

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

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

%e - | | | that is the concatenation of | | and | |

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

%e Hence a(4)=1.

%Y Cf. A000045 (Fibonacci numbers).

%Y Cf. A225202.

%K nonn

%O 1,3

%A _Paul Tek_, May 04 2013