Enumeration of 4-stack polyominoes. (English) Zbl 1301.05063
Summary: 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 \(\sqrt 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.
References:
| [1] | Bousquet-Mélou, M., A method for the enumeration of various classes of column convex polygons, Discrete Math., 154, 1-25 (1996) · Zbl 0858.05006 |
| [2] | Castiglione, G.; Frosini, A.; Munarini, E.; Restivo, A.; Rinaldi, S., Combinatorial aspects of L-convex polyominoes, European J. Combin., 28, 1724-1741 (2007) · Zbl 1120.05018 |
| [3] | Castiglione, G.; Frosini, A.; Restivo, A.; Rinaldi, S., Enumeration of L-convex polyominoes by rows and columns, Theoret. Comput. Sci., 347, 336-352 (2005) · Zbl 1080.68082 |
| [4] | Castiglione, G.; Restivo, A., Reconstruction of L-convex polyominoes, (Electron. Notes Discrete Math., vol. 12 (2003), Elsevier Science) · Zbl 1173.68761 |
| [5] | Delest, M.; Viennot, X., Algebraic languages and polyominoes enumeration, Theoret. Comput. Sci., 34, 169-206 (1984) · Zbl 0985.68516 |
| [6] | Duchi, E.; Rinaldi, S.; Schaeffer, G., The number of Z-convex polyominoes, Adv. Appl. Math. Mech., 4, 54-72 (2008) · Zbl 1133.05019 |
| [7] | Dutour, I.; Fédou, J.-M., Object grammars and bijections, Theoret. Comput. Sci., 290, 1915-1929 (2003) · Zbl 1044.68075 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
