Skip to content (access key 's')
Logo of Technion
Logo of CS Department


Enumeration of Lattice Animals
event speaker icon
Gadi Aleksandrowicz, Ph.D. Thesis Seminar
event date icon
Sunday, 30.1.2011, 13:00
event location icon
Taub 337
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]