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

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

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

Example

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.

Crossrefs

Cf. A000045 (Fibonacci numbers).

Cf. A225202.

Sequence in context: A287755 A051258 A063704 * A224508 A360894 A116891

Adjacent sequences: A224915 A224916 A224917 * A224919 A224920 A224921

Keyword

nonn

Author

Paul Tek, May 04 2013

Status

approved