Stephan Mertens - Research Home | Research | Publications | Teaching | Smorgasbord

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

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

• Counting Lattice Animals in High Dimensions (with S. Luther)
  J. Stat. Mech. P09026 (2011) PDF BibTeX

In these older papers we describe the basic algorithm, its efficient and parallel implementation:

• Counting Lattice Animals: A Parallel Attack (with M.E. Lautenbacher)
  J. Stat. Phys. 66, 669-678 (1992) PDF BibTeX
• Lattice Animals: A Fast Enumeration Algorithm and New Perimeter Polynomials
  J. Stat. Phys. 58, 1095-1108 (1990) PDF BibTeX

Data

Perimeter Polynomials

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

The coefficients G_n to compute the formula for the perimeter polynomials for arbitrary dimension d and fixed size n are listed in the following files:

n	2	3	4	5	6	7	8	9	10	11	12
Gn	G2.dat	G3.dat	G4.dat	G5.dat	G6.dat	G7.dat	G8.dat	G9.dat	G10.dat	G11.dat	G12.dat

Cluster Numbers and Series Expansions

The file Ad_poly.txt contains the polynomials to compute the number A_d(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
3	A3.dat	A001931	S3.dat	A003211
4	A4.dat	A151830	S4.dat
5	A5.dat	A151831	S5.dat
6	A6.dat	A151832	S6.dat
7	A7.dat	A151833	S7.dat
8	A8.dat	A151834	S8.dat
9	A9.dat	A151835	S9.dat
10	A10.dat		S10.dat

Source Code

Redelemeier's algorithm for the enumeration of perimeter polynomials in hypercubic lattices:

• create_lattice.cpp
• redelmeier.cpp
• Makefile
• README

All files: redelmeier.tar.
See README for details.