greenline
rgstripes
Otto-Bild Stephan Mertens - Research
Home | Research | Publications | Teaching | Smorgasbord
greenline

Lattice Animals

A lattice animal is a finite set of connected vertices of a regular lattice. Lattice animals on the square lattice are better known as polyominoes. On the cubic lattice they are called polycubes. The figure above shows all possible polycubes of size n = 4.

The enumeration of lattice animals is a longstanding combinatorial problem that has some motivations in physics, for example in the study of branched polymers and percolation. For most lattices we don't know a formula for the number of lattice animals of a given size n, and all we can do is to count them one by one. Since the number of lattice animals grows exponentially with n, this counting is a demanding task, even with a fast computer.

We develop fast algorithms for the enumeration of lattice animals, and we run these algorithms on parallel computers. We also work out combinatorial arguments that complement computer based enumerations.

Please check out the publications if you want to learn more about the problem and our algorithms. If you are an expert, you might want to go directly to the enumeration data or to the source code.

Publications

New enumerations and analytical results for the number of bond animals on hypercubic lattices: The algorithm and the combinatorial arguments that have been used to compute the data for hypercubic lattices in dimensions d ≥ 3 on this webpage are described in In these older papers we describe the basic algorithm, its efficient and parallel implementation:

Data

Perimeter Polynomials for Site Animals

The file perimeterpolynomials.tar contains a folder for each dimension d=3..10, each folder contains files "perimeter.n" for the coefficients gn,t.

The coefficients Gn to compute the formula for the perimeter polynomials for arbitrary dimension d and fixed size n are listed in the following files:
n234 5678 9101112
Gn G2.dat G3.dat G4.dat G5.dat G6.dat G7.dat G8.dat G9.dat G10.dat G11.dat G12.dat

Perimeter Polynomials for Bond Animals

The file gd_bond.dat contains the number of bond animals in dimension d of size e, perimeter t and number of vertices v.
e234 5678 91011
gg g2_bond.dat g3_bond.dat g4_bond.dat g5_bond.dat g6_bond.dat g7_bond.dat g8_bond.dat g9_bond.dat g10_bond.dat g11_bond.dat

The coefficients Ge,t,v to compute the formulas for the perimeter polynomials for arbitrary dimension d and fixed size e are listed in the following files:
e234 5678 91011
Ge G2_bond.dat G3_bond.dat G4_bond.dat G5_bond.dat G6_bond.dat G7_bond.dat G8_bond.dat G9_bond.dat G10_bond.dat G11_bond.dat

Cluster Numbers and Series Expansions for Site Animals

The file Ad_poly.txt contains the polynomials to compute the number Ad(n) for given size n and arbitrary dimension d. We know these formulas up to n=14.

cluster numbers Ad(n)cluster series Sd
d data OEIS data OEIS
3A3.datA001931 S3.datA003211
4A4.datA151830 S4.dat
5A5.datA151831 S5.dat
6A6.datA151832 S6.dat
7A7.datA151833 S7.dat
8A8.datA151834 S8.dat
9A9.datA151835 S9.dat
10A10.dat S10.dat

Source Code

Python scripts to compute Gn,tn-1 and Gn,tn-2, the number of polycubes (lattice animals) of size n and perimeter t, that are proper in dimension n-1 or dimension n-2. Redelemeier's algorithm for the enumeration of bond- and site-animals in hypercubic lattices: See README for details, how to compile and use the software (including parallelization on distributed or shared memory computers).

greenline
rgstripes
top Home | Research | Publications | Teaching | Smorgasbord
greenline

© by Stephan Mertens (Datenschutzerklärung)
updated on Friday, October 26th 2018, 10:06:23 CET;