Andrei Asinowski, Gill Barequet, Gil Ben-Shachar, Martha Carolina Osegueda, and Günter Rote:

On the number of compositions of two polycubes

1. Computing in Geometry and Topology 3, no. 1 (2024), 4:1–4:18. doi:10.57717/cgt.v3i1.41  →BibTeX
2. Preliminary version in: Extended Abstracts EuroComb 2021, European Conference on Combinatorics, Graph Theory and Applications, Editors: Jaroslav Nešetřil, Guillem Perarnau, Juanjo Rué, and Oriol Serra, Springer-Verlag, 2021, pp. 71–77. doi:10.1007/978-3-030-83823-2_12  →BibTeX

Abstract

We provide almost tight bounds on the minimum and maximum possible numbers of compositions of two polycubes of given total size, in two and higher dimensions. In the plane, we reach a near-quadratic number of compositions. We also provide an efficient algorithm (with some trade-off between time and space) for computing the number of composition of two given polyominoes (or polycubes).