A056840

[Joseph S. Myers]

On Sun, 26 Oct 2003, David Wasserman wrote:

> Dear Seqfans,
>       I think A056840 looks like an incorrect version of A030222.  Does
> anyone have a better explanation for it?

There is a figure for n=5 (the first term where the sequences differ) on
the referenced web page
<http://alpha.ujep.cz/~vicher/puzzle/polyform/minio/images/r7.gif>.

I think the following explanation applies for A056840, but someone should
do the computations to verify it (and probably compute counts for "fixed"
shapes - orientation matters - and one-sided shapes - at the same time,
and add those sequences if not present).  Consider a polyplet (A030222) as
made up of n components which are polyominoes, those polyominoes being
joined to each other only at corners.  Then sever all but n-1 of the
diagonal links in such a way that a spanning tree remains.  A056840 counts
the number of such spanning trees (where different orientations of the
same spanning tree don't count as distinct; note that a single symmetrical
polyplet can produce multiple identical spanning trees of lesser symmetry
in different orientations, which count as the same).

Similarly, A056841 appears to count spanning trees of polyominoes
(ordinary polyominoes, A000105), where the edges shared by two squares are
the edges of the graph for the purposes of forming the spanning tree, and
A056787 (with the cryptic description "n-node tree graphs with diagonals -
related to pseudopolyominoes" and marked "obsc") _may_ count spanning
trees of polyplets where the graph has edges joining every pair of squares
that share an edge or vertex (this definitely needs computations, but it
does match the first three terms).

-- 
Joseph S. Myers
jsm28 at cam.ac.uk