Enumeration of 4-stack polyominoes

In this paper, we consider the class of 4-stack polyominoes, i.e. polyominoes which can be decomposed into a central rectangle supporting four stack polyominoes, one on each side of the rectangle. This class of objects - recently introduced by Marc Noy - extends the class of centered convex polyominoes, and is included into the class of Z-convex polyominoes. Using an inclusion/exclusion approach, we obtain the enumeration of 4-stack polyominoes according to the number of rows and columns. Moreover, we solve some problems posed by Marc Noy, proving that the generating function of 4-stack polyominoes according to the semi-perimeter is algebraic, and that their asymptotic behavior is root n4(n), which is immediately smaller than the asymptotic behavior of Z-convex polyominoes, which is n4(n). As a corollary of our result, we find the generating function of bi-centered polyominoes, i.e. convex polyominoes which are both horizontally and vertically centered. (C) 2011 Elsevier B.V. All rights reserved.