**NC State University**

**
Department of Computer Science Colloquia Series 1998-99**

**Date:** Thursday, October 29, 1998

**Time: ** 3: 30 PM (refreshments), 4:00 PM (talk)

**Place: ** Withers 402A, NCSU Historical Campus
(click
for courtesy parking request)
**Speaker:** Sylvie Corteel, Universite Paris-Sud, LRI, Orsay, France

**
The Bousquet-Conway Directed Animals
**

**Abstract: **
A {\em directed animal} $A$ is a finite set of vertices on an
acyclic infinite periodic lattice $L$ such that any vertex of $A$ can
be reached from a distinguished vertex, called the source, through an
oriented path of $L$ having all its vertices in $A$. Animals are
defined up to a translation on the lattice. Bousquet-Melou and Conway
found algebraic equations for the area generating function of directed
animals on an infinite family of regular, non-planar, two-dimensional
lattices by using equivalences with hard particle models (statistical
physics techniques.) We give in this paper a bijective proof of their
results which is a generalization of Viennot's heaps of pieces. Thanks
to this proof we can get some exact enumeration formulas for the number
of configurations with $n$ vertices which could not be deduced directly
from the algebraic equation and did not appear in earlier work. Moreover,
we give an extension of these results to another infinite family
of regular, non-planar, two-dimensional lattices.

This represents joint work with Alain Denise and Dominique
Gouyou-Beauchamps at LRI, Orsay.

**Short Bio: **
Sylvie Corteel received her undergraduate degree in Computer
Science at Compiegne and her M.S. in Computer Science from N.C. State
in May 1997. She is currently working on her Ph.D. thesis at the
Universite Paris-Sud, Laboratoire de Recherche en Informatique (LRI)
in Orsay, France. Her research interests are in combinatorics and combinatorial
computing and to date she is co-author of four journal articles and two
conference papers in these areas.

Colloquia Home Page.