0,2

Hugo van der Sanden, Table of n, a(n) for n = 0..100

Let u(n) represent the number of decompositions of a 1 x n rectangle. Then:

u(n) = 2^(n-1) for n > 0, u(n) = 1 for n = 0.

Let t(n) represent the number of decompositions of a 2 x n rectangle such

that a single piece includes the whole of the leftmost and rightmost columns.

Then:

t(n) = t(n-2) + sum_1^{(n-3)/2}{ 2 u(i)^2 t(n-2i-2) }

Let s(m, n) represent the number of decompositions of a 2 x n rectangle with

a 1 x m spike attached to the side. Then for m > 0:

s(m, n) = sum_1^m{ s(m-i, n) } + sum_1^n{ s(i, n-i) }

+ sum_m^{(n+m-1)/2}{ u(i-m) sum_1^{n+m-2i}{ t(j) s(i, n+m-2i-j) } }

and for m = 0:

s(m, n) = sum_1^n{ s(i, n-i) } + sum_1^n{ t(i) s(0, n-i) }

+ sum_1^{(n-1)/2){ u(i) sum_1^{n-2i}{ t(j) s(i, n-2i-j) } }

(Note that these sums can be taken to infinity if the functions are defined

as zero when any argument is negative.) We get

t(n) = [ 0 1 1 1 1 3 3 13 13 59 59 269 269 1227 1227 5597 5597 25531 ... ] = A052984((n - 3) / 2)

with recurrence a(n) = 5a(n-1)-2a(n-2), a(0) = 1, a(1) = 3.

This gives a much faster way to calculate values for the sequence (as s(0, n))

Example: the partitions comprising a(2)=8 are:

AA AA AB AA AB BC BA AB

AA BB AB BC AC AA CA CD

I.e. exactly those of A078469(2)=12 except for the 4 rotations of the one partition that includes an asymmetric piece:

AA

AB

Cf. A078057, A152113.

Sequence in context: A123290 A088675 A027743 this_sequence A147722 A089387 A084868

Adjacent sequences: A152121 A152122 A152123 this_sequence A152125 A152126 A152127

nonn

Hugo van der Sanden (hv at crypt.org), Mar 23 2009