[seqfan] Re: Two-fold symmetry sequence
Joseph S. Myers
jsm at polyomino.org.uk
Mon Dec 29 23:33:49 CET 2008
On Mon, 29 Dec 2008, Frederick Schneider wrote:
> Here's an image explaining what I mean:
>
> http://www.bosola.org/grandpa/imgs/2-foldSymmetry.jpg
>
> Has anyone seen a similar sequence? If not, I'll try to extend this at
> least a few terms out.
This (free polyominoes with at least c2 symmetry) would be the sum of the
columns "all", "axis 2", "rotate 2", "diag 2" and "rotate" from
Redelmeier's Table 3 (in Counting polyominoes: yet another attack,
Discrete Math. 36 (1981) 191-203) which respectively count those whose
symmetries are exactly d4, d2 (horizontal and vertical reflections), c4,
d2 (diagonal reflections) and c2. "axis 2" is A056877, "diag 2" is
A056878, "rotate" is A006747. The columns for polyominoes without c2
symmetry are also present , "axis" (A006746), "diag" (A006748), "none"
(A006749). For some reason, "all" and "rotate 2" seem to be missing.
(Those sequences are zero for n = 2 or 3 mod 4 so it's not clear what
versions should be present - for all n? n = 0 and 1 mod 4 only? n = 0
mod 4 and n = 1 mod 4 in separate sequences? But none of these variants
seem to be present.) An image of the table is attached.
Tomas Oliveira e Silva could likely provide versions of the missing
sequences up to n=28 (Redelmeier gives them to n=25), though I can't find
counts of symmetric polyominoes on his webpages. The figures for "at
least" a given symmetry, such as your sequence, would seem to be worth
adding as well if not already present.
Incidentally, it should be possible to implement Redelmeier's algorithms
for counting symmetric polyominoes and to combine those with the
enumeration of fixed polyominoes (A001168) up to n=56 by the transfer
matrix method in order to extend the numbers for free polyominoes
(A000105) up to n=56 or pretty near that (from the present limit of n=28);
the counts involving symmetry groups of order 4 or 8 should be extendable
well beyond that. Though counting symmetric polyominoes is more
complicated than counting free polyominoes, and Redelmeier doesn't give
the details of the algorithms he used for counting rings where
connectivity issues come in. (Converting numbers of fixed polyominoes
with "at least" a given symmetry, as given by these algorithms, to numbers
of fixed polyominoes with exactly a given symmetry, and so to free
polyominoes with exactly a given symmetry, is routine linear manipulation
of obvious formulae giving "at least" in terms of "exact".)
--
Joseph S. Myers
jsm at polyomino.org.uk
More information about the SeqFan
mailing list