[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