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

1, 1, 2, 1, 7, 0, 20, 9, 28, 9, 143, 39, 376, 105, 340, 441, 2583, 480, 6764, 2400, 7235, 6897, 46367, 10332, 88625, 50193, 151436, 126504, 832039, 127431, 2178308, 974169, 2618488, 2484873, 9209899, 3202560, 39088168, 17218617, 47865787, 33738201, 267914295, 49047180, 701408732, 303913896, 624579100

Offset: 1

Author

Paul Tek, May 04 2013

Keywords

• nonn

Comments

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

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

a(n) <= A225202(n).

Examples

			A 4 x 1 rectangle can be tiled in 5 ways:
  +-+-+-+-+                               +-+  +-+  +-+     +-+
- | | | | | that is the concatenation of  | |, | |, | | and | |
  +-+-+-+-+                               +-+  +-+  +-+     +-+,
  +---+-+-+                               +---+     +-+-+
- |   | | | that is the concatenation of  |   | and | | |
  +---+-+-+                               +---+     +-+-+,
  +-+---+-+
- | |   | | that is not the concatenation of smaller equally sized tilings,
  +-+---+-+
  +-+-+---+                               +-+-+     +---+
- | | |   | that is the concatenation of  | | | and |   |
  +-+-+---+                               +-+-+     +---+,
  +---+---+                               +---+     +---+
- |   |   | that is the concatenation of  |   | and |   |
  +---+---+                               +---+     +---+.
Hence a(4)=1.
		

Links

• Paul Tek, Table of n, a(n) for n = 1..1000
• Paul Tek, Illustration of the first terms
• Paul Tek, PERL program for this sequence

Crossrefs

Cf. A000045 (Fibonacci numbers).

Cf. A225202.