[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