[seqfan] 2-d partitions, rotationally symmetric pieces
hv at crypt.org
hv at crypt.org
Mon Mar 23 09:46:22 CET 2009
All the points below involve connected pieces consisting of unit squares
cut along lattice lines, as 2-d analogues of the integers used for partitions.
1. A078469 "Number of different compositions of the ladder graph L_n."
This is identically the number of partitions of the 2 x n rectangle.
I feel the entry for a(0) = 0 should be 1 instead, though it does throw
out the start of the recurrence.
2. The number of ways to decompose the 1 x n rectangle into pieces each
of which has rotational symmetry is trivially 2^(n - 1).
3. The number of distinct pieces with rotational symmetry that extend
to opposite corners of a 2 x n rectangle satisfies the recurrence relation
a(2n) = a(2n + 1) = 2a(2n-2) + a(2n-4): [n=1]: 1, 1, 3, 3, 7, 7, 17, 17, ...
Example: the pieces comprising a(3) are:
AAA BB. .CC
AAA .BB CC.
4. The number of ways to decompose the 2 x n rectangle into pieces each
of which has rotational symmetry is the following sequence:
[n=0]: 1, 2, 8, 36, 162, 746, 3420, 15738, 72352, 332850,
[n=10]: 1530928, 7042422, 32394478, 149015678, 685471704, 3153185542,
14504703924, 66721946584, 306922286796, 1411848979422
[n=20]: 6494534685710, 137425609255358, 632160693109496, 2907952479953454,
13376642577294978, 61532837218960114, 283052345606879420,
1302046743996675526 [n=28]
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
[4a: is there a general technique, when you think it likely a sequence
exhibits a recurrence relation, to discover what the relation is given
sufficient values? Clearly an order-n recurrence will yield a matrix of
simultaneous equations given 2n-1 consecutive values, but I'm guessing
that prior art might help shortcircuit the effort.]
5. Representing the partitions in (4) by the set of centres of rotation
of the pieces, the representation is unique for all partitions up to a(8).
An ambiguous pair on the 2 x 9 rectangle are:
AAAAAABAA AAAAABBBA
AACAAAAAA ACCCAAAAA
I'm not sure that re-counting the sequence in (4) with this extra
constraint is additionally interesting enough to be worth the effort:
I'd rather go on to tackle 3 x n and larger.
This train of though was inspired by a new puzzle-type on janko.at,
"Galaxien": http://www.janko.at/Raetsel/Galaxien/index.htm
Hugo
More information about the SeqFan
mailing list