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

The Taub Faculty of Computer Science Events and Talks

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