Enumeration of Lattice Animals

Gadi Aleksandrowicz, Ph.D. Thesis Seminar
Sunday, 30.1.2011, 13:00
Taub 337
Prof. G. Barequet

A Lattice Animal is a set of edge-connected cells in a given lattice. For example, the Tetris game is played with Lattice Animals with 4 cells in the two-dimensional orthogonal lattice. The enumeration of Lattice Animals is a long-time standing problem, arising in all of recreational mathematics, discrete geometry, and statistical physics. In this talk I will discuss a generalization of Redelmeier's algorithm to the enumeration of polyominoes that lie on any structural (repetitve) lattice. I will also present a bijection between polyominoes and permutations, and describe the enumeration of several families of polyominoes through couting classes of permutations that avoid some sets of "forbidden patterns". In addition, I will apply a transfer-matrix method to polyominoes on a twisted cylinder in order to derive the generating functions of the sequence that enumerates these polyominoes.

Back to the index of events