# Enumeration of minimal 3D polyominoes inscribed in a rectangular prism

Alain Goupil$^{1†}$and Hugo Cloutier$^{1‡}$

$^{1}$Département de mathématiques et d'informatique, Université du Québec à Trois-Rivières, Canada

**Abstract.** We consider the family of 3D minimal polyominoes inscribed in a rectangular prism. These objects are polyominos and so they are connected sets of unitary cubic cells inscribed in a given rectangular prism of size $b \times k \times h$ and of minimal volume equal to $b + k + h - 2$. They extend the concept of minimal 2D polyominoes inscribed in a rectangle studied in a previous work. Using their geometric structure and elementary combinatorial principles, we construct rational generating functions of minimal 3D polyominoes. We also obtain a number of exact formulas and recurrences for sub-families of these polyominoes.

**Résumé.** Nous considérons la famille des polyominos 3D de volume minimal inscrits dans un prisme rectangulaire. Ces objets sont des polyominos et sont donc des ensembles connexes de cubes unitaires. De plus ils sont inscrits dans un prisme rectangulaire de format $b \times k \times h$ donné et ont un volume minimal égal à $b + k + h - 2$. Ces polyominos généralisent le concept de polyomino 2D étudié dans un travail précédent. Nous construisons des séries génératrices rationnelles de polyominos 3D minimaux et nous obtenons des formules exactes et des récurrences pour des sous-familles de ces polyominos.

**Keywords:** polycube, inscribed polyomino, enumeration, rectangular prism, generating function, minimal volume.

## 1 Introduction

Since the rise of modern combinatorics in the early 1960's, most combinatorial objects are visualized and investigated with pencil and paper and therefore, are 2-dimensional. Despite this natural inclination, a number of extensions from 2D combinatorial objects to 3D objects were introduced: Ferrers diagrams were extended to plane partitions, permutations were extended to maps on a surface and to braids, 2D fractals were extended to 3D fractals and a short list of exact enumerative results for 3D objects have been produced so far (see [1],[7]). Behind these efforts lay a fundamental question: Is 3D combinatorics a natural extension of notions and concepts already known in 2D combinatorics or does it introduce new concepts unknown in 2D combinatorics ? This question was part of our motivation to begin a study of 3D inscribed polyominoes.

A 2D-polyomino is a 4-connected set of unit square cells in the discrete plane. That is, the cells are connected by their edges. A polyomino is inscribed in a $b \times k$ rectangle when it is contained in this

<footnote>†Work supported in part by NSERC. alain.goupil@uqtr.ca</footnote>

<footnote>‡hugo854@yahoo.ca</footnote>
<figure><img src="image_1.png" /><figcaption>**Fig. 1: 2D and 3D inscribed minimal polyominoes**</figcaption></figure>

rectangle and touches each of its four sides. Inscribed 2D polyominoes with minimal area were introduced in a previous work (see [4]) where an elementary geometric characterization was given that permitted their enumeration and the construction of their generating functions. The geometry of an inscribed minimal 2D polyomino can be described in simple terms as a *hook-stair-hook* structure where a hook is formed with two mutually perpendicular rows of cells starting on an edge of the rectangle and meeting at their corner end to end in the opposite corner of the rectangle (see fig. 3(a) red cells and [4] for more details). A 2D *stair* is a path of connected cells beginning on one corner of a rectangle, say north-west, and moving along the corresponding diagonal in the east - south direction (see fig. 3(a), black cells and their circumscribed rectangle).

3D polyominoes, sometimes called polycubes, are known in the literature and in recreational mathematics in the context of packing problems (see [2]) and their enumeration according to their volume is known up to volume 16 in [3] as the result of a computer program. However combinatorial enumeration of inscribed 3D polyominoes does not seem to have been considered so far.

We define 3D polyominoes inscribed in a rectangular $b \times k \times h$ prism as collections of unit 6-connected cubic cells contained in the prism and touching each of its six faces. We give a geometric description of a complete collection of families of inscribed 3D polyominoes with minimal volume. This allows us to present generating functions, recurrences and exact formulas these families. One fundamental principle used throughout this work to enumerate inscribed 3D polyominoes is the fact that they can be broken in elementary parts easier to describe and used as building blocks with the multiplication principle.

We will introduce three disjoint families of minimal 3D inscribed polyominoes and show that their union forms a complete set of 3D inscribed polyominoes with minimal volume. These three families will be called respectively *3D diagonal poliominoes*, 2D × 2D polyominoes and *skew cross* polyominoes.

We will use the orthogonal projection of inscribed 3D polyominoes on the upper face of the prism in view of the fact that an inscribed 3D polyomino is of minimal volume if and only if its orthogonal projection on each face of the circumscribed prism is a 2D polyomino of minimal area. This is easily proved by contradiction for if a 3D inscribed polyomino is not minimal, then one of its projections is not 2D minimal. Similarly, if one projection is not minimal, then the 3D polyomino cannot be minimal.

**Notations** We will use capital letters for sets and generating functions and their corresponding lower case letters will be used for set cardinalities. For example $P_{3D,min}(b, k, h)$ will denote the set of 3D polyominoes inscribed in a $b \times k \times h$ rectangular prism with minimal volume, $p_{3D,min}(b, k, h)$ will be
their number and $P_{3D,min}(x, y, z) = \sum_{b,k,h} p_{3D,min}(b, k, h)x^b y^k z^h$ will be their generating function. We will use the convention that the edge of length b of the prism is along the x axis and similarly the lengths k, h are along the y and z axis respectively.

The degree of a 3D cell c in a polyomino, denoted deg(c), is the number of cells having a face in contact with c and the degree of a 2D cell c is the number of cells with an edge contact with c. All polyominoes considered in this paper are 2D or 3D, always inscribed in a rectangle or a rectangular prism and of minimal area or volume. Therefore we will often omit to specify these constraints on polyominoes. We will use trinomial coefficients in their standard notation $\binom{a+b+c}{a,b,c}$. We refer the reader to [4] for results and definitions on 2D polyominoes.

The paper is organized as follow. In section 2, we introduce diagonal 3D polyominoes and the subfamilies needed for their geometric description. We give generating functions, recurrences and exact formulas for these subfamilies. In section 3, we define two families of non diagonal polyominoes: $2D \times 2D$ polyominoes and skew cross polyominoes. We give their generating functions and some exact formulas. In section 4, we sketch the proof of the main result of the paper which states that these three families of polyominoes form a complete set of 3D minimal inscribed polyominoes.

## 2 Diagonal polyominoes

In similarity with 2D stairs, we define a 3D stair as an inscribed polyomino of minimal volume forming a path starting in a given corner of the prism, say the north-west-back corner, and moving with unit steps in the south, east or forward direction until it reaches the opposite 3D diagonal corner as in figure 2(d). In what follows, we will use 3D stairs as components of polyominoes.

A 2D corner-polyomino is a 2D minimal polyomino inscribed in a rectangle with a cell in a given corner of the rectangle. The number $P_c(b, k)$ of 2D corner-polyominoes inscribed in a $b \times k$ rectangle satisfies the following recurrence and exact formula:

$$P_c(b, k) = 1 + P_c(b, k-1) + P_c(b-1, k) = 2\binom{b+k-2}{b-1} - 1 \quad (1)$$

with initial conditions $P_c(b, 1) = P_c(1, k) = 1$. Its generating function has the rational form

$$P_c(x, y) = \sum_{b,k \ge 1} P_c(b, k) x^b y^k = \frac{2xy}{(1-x-y)} - \frac{xy}{(1-x)(1-y)} \quad (2)$$

Recall also (see [4]) that the total number of polyominoes of minimal area inscribed in a rectangle $p_{2D,min}(b, k)$ of size $b \times k$ is given by the formula

$$p_{2D,min}(b, k) = 8\binom{b+k-2}{b-1} + 2(b+k) - 3bk - 8$$

We first define and investigate 3D corner-polyominoes. A 3D corner-polyomino is a minimal polyomino inscribed in a prism with one cell in a given corner of the prism, say the north-west-back corner. Let $P_c(b, k, h)$ be the set of corner-polyominoes inscribed in a $b \times k \times h$ prism.
<figure><img src="image_2.png" /><figcaption>Fig. 2: Corner polyominoes</figcaption></figure>

**Theorem 1** For all positive integers $b, k, h$, the number $p_c(b, k, h)$ of 3D corner-polyominoes inscribed in a prism of size $b \times k \times h$ with minimal volume satisfies the following recurrence :

$$p_c(b, k, h) = \begin{cases} 2\binom{b+k+h-3}{b-1,k-1,h-1} - 1 & \text{if } b=1 \text{ or } k=1 \text{ or } h=1 \\ 1 + 2\binom{b+k-2}{b-1} + 2\binom{b+h-2}{b-1} + 2\binom{k+h-2}{k-1} - 6 & \\ + p_c(b-1, k, h) + p_c(b, k-1, h) + p_c(b, k, h-1) & \text{otherwise} \end{cases}$$

**Proof:** The first case is the 2D case. It provides the initial conditions for the 3D case and is obtained from equations (1). In the second case, observe that a corner cell has degree one, two or three. There is exactly one 3D corner-polyomino with corner of degree three inscribed in a $b \times k \times h$ prism and we call this polyomino a *tripod*. This explains the term 1 in the recurrence. When the corner cell $c$ is of degree two, then $c$ is the corner cell of a 2D corner-polyomino different from a 2D hook that is inscribed in a face of the prism and attached to a perpendicular row of cells along an edge of the prism. A row of cells connecting the polyomino to a face of the prism will often be considered and we will call these components *pilars*. Figure 2(b) illustrates this situation: the corner cell of degree two is the red cell, the 2D corner-polyomino is made of the red and blue cells and the set of green cells forms a pilar. The next four terms in the recurrence are thus deduced from equation (1) Now if the corner $c$ has degree one, as in figure 2(c), then the polyomino starts with a 3D stair giving the last three terms of the recurrence. $\square$

Observe that the separation according to the degree of the corner cell also gives the following equivalent formulation for the recurrence:

$$\begin{aligned} P_c(b, k, h) &= tripod + (2D\text{-corner} - 2D\text{-hook}) + deg1 \\ &= 1 + (P_c(b, k, 1) + P_c(b, 1, h) + P_c(1, k, h) - 3) + (P_c(b, k, h-1) + P_c(b, k-1, h) + P_c(b-1, k, h)) \end{aligned}$$

**Generating functions** To establish the generating function for the set of 3D corner-polyominoes, we will first give the generating functions $Stair(x, y, z)$, $Tripod(x, y, z)$, $2dhook(x, y, z)$ and $Deg2(x, y, z)$ which are respectively 3D stairs, tripods, 2D hooks and 3D corner-polyominoes of degree two:

$$Tripod(x, y, z) = \sum_{i,j,k \ge 2} x^i y^j z^k = \frac{x^2 y^2 z^2}{(1-x)(1-y)(1-z)}$$
$$
\begin{align*}
\mathrm{Stair}(x, y, z) &= \sum_{i,j,k \ge 1} \binom{i+j+k-3}{i-1,j-1,k-1} x^i y^j z^k = xyz \sum_{n \ge 0} (x+y+z)^n = \frac{xyz}{(1-x-y-z)} \\
2\mathrm{Dhook}(x, y, z) &= \frac{x^2 y^2 z}{(1-x)(1-y)} + \frac{x^2 y^2 z^2}{(1-x)(1-z)} + \frac{xy^2 z^2}{(1-z)(1-y)} \\
\mathrm{Deg2}(x, y, z) &= \left[ \frac{2yz}{(1-y-z)} - \frac{2yz}{(1-y)(1-z)} \right] \frac{x^2}{(1-x)} + \tag{3} \\
&\quad \left[ \frac{2xz}{(1-x-z)} - \frac{2xz}{(1-x)(1-z)} \right] \frac{y^2}{(1-y)} + \left[ \frac{2xy}{(1-x-y)} - \frac{2xy}{(1-x)(1-y)} \right] \frac{z^2}{(1-z)}
\end{align*}
$$

The proof for the rational form of these generating functions is straightforward once we understand the geometric nature of the corresponding objects: there is one tripod per prism because, by definition, their corner cell is in a given corner of the prism. The number of stairs from one corner to its diagonal opposite corner in a prism of size $b \times k \times h$ is equal to the trinomial coefficient $\binom{b+k+h-3}{b-1,k-1,h-1}$. 2D-hooks appear on a slice parallel to one of the faces so we have three terms, one for each coordinate plane. The generating function for corner-polyominoes of degree two (equation (3)) is directly obtained from its definition: a 2D corner of degree one perpendicular to a *pilar*.

Now we are ready to use these building blocs. For instance a 3D corner of degree one always begins as a 3D stair of length at least two connected to a 3D corner of any degree. The generating function $\mathrm{Deg1}(x, y, z)$ of 3D corners of degree one is thus

$$ \mathrm{Deg1}(x, y, z) = (\mathrm{Stair}(x, y, z) - xyz)(1 + \mathrm{Tripod} + \mathrm{Deg2} + 2\mathrm{Dhook}) $$

Since we now have the generating functions for corner-polyominoes of degree one, two and three, we deduce the following result.

**Proposition 1** *The generating function $P_c(x, y, z)$ for 3D corner-polyominoes is the following:*

$$
\begin{align}
P_c(x, y, z) &= \sum_{b,k,h \ge 1} p_c(b, k, h) x^b y^k z^h \nonumber \\
&= \mathrm{Stair}(x, y, z) \left[ 1 + \frac{\mathrm{Tripod}(x, y, z) + \mathrm{Deg2}(x, y, z) + 2\mathrm{Dhook}(x, y, z)}{xyz} \right] \tag{4}
\end{align}
$$

**Proof:** This is an immediate consequence of the fact that a 3D corner-polyomino is the connection of a 3D stair with a 3D corner-polyomino of arbitrary degree. $\square$

**Theorem 2** For all positive integers $b, k, h$, we have

$$
\begin{align}
p_c(b, k, h) &= 4 \binom{b+h-2}{h-1} \binom{b+k+h-3}{b+h-2} + \sum_{i=0}^{h-2} (-1)^i \binom{b+h-4-2i}{h-2-i} \binom{b+k+h-4-i}{b+h-3-2i} \nonumber \\
&\quad -2 \left[ \binom{b+h-2}{b-1} + \binom{b+k-2}{k-1} + \binom{k+h-2}{h-1} \right] + 3 - \frac{(1+(-1)^h)}{2} \tag{5}
\end{align}
$$
**Proof:** (Sketched) By induction on $b + k + h$. If $h = 1$ then the prism is reduced to a rectangle in the $xy$ plane and formula (5) gives $p_c(b, k, 1) = 2\binom{b+k-2}{b-1} - 1$ which agrees with equation (1). The same argument is true for $b = 1$ and $k = 1$. Suppose that formula (2) is true for a prism of size $b \times k \times h$ with $b, k, h \ge 2$. We have

$$p_c(b, k, h+1) = 1 + 2\binom{b+k-2}{b-1} + 2\binom{b+h-1}{b-1} + 2\binom{k+h-1}{k-1} - 6 + p_c(b-1, k, h+1) + p_c(b, k-1, h+1) + p_c(b, k, h)$$

by theorem 1 and by induction hypothesis we obtain expression (5). □

It is now possible to construct formulas for the set of polyominoes along one given diagonal of the prism. We define *diagonal polyominoes* as inscribed polyominoes of minimal volume formed with three pieces: two hooks on each end of a diagonal of the prism connected by a stair in contact with their corner cell (see figure 1(b)). By a hook we mean either a 3D corner-polyomino with corner of degree two or three or a 2D hook. From this definition, we deduce the rational form of the generating function of diagonal polyominoes.

**Proposition 2** *The generating function $1Diag(x, y, z)$ of diagonal polyominoes along one given diagonal of a prism is the following*

$$1Diag(x, y, z) = Stair(x, y, z) \left[ 1 + \frac{Tripod(x, y, z) + Deg2(x, y, z) + 2Dhook(x, y, z)}{xyz} \right]^2 \quad (6)$$

**Proof:** This is a direct consequence of the definition of diagonal polyominoes, tripods, stairs, corner-polyominoes and 2D hooks. The number 1 inside the brackets of equation (6) stands for the fact that 3D hooks could be absent and we divide by $xyz$ the next term because we arbitrarily decide that the cell common to a hook and a stair belongs to the stair so that we remove it from the hook with this division. □

In the next step, we count the total number of diagonal polyominoes in a prism. There are four 3D diagonals in a prism. If a polyomino belongs to exactly two diagonals, then the two diagonals always define a plane perpendicular to two parallel faces of the prism. The orthogonal projection of the polyomino on these faces must be a 2D minimal polyomino and therefore this projection has the generic form *hook-stair-hook* of a 2D minimal polyomino. The projection of the two 3D diagonals on any other face are the two diagonal of these rectangles. Since the only 2D polyomino that belongs to two diagonals of a rectangle is a 2D cross, the projection of the polyomino on the other faces is always a 2D cross. This has consequences on the form of any 3D polyomino along two diagonals which must be made of a *full pilar*, i.e. a pilar connecting two opposite faces, connected to a perpendicular 2D generic polyomino inscribed in a full 2D slice of the prism (see the blue part in figure 3(b)). Moreover the full pilar must meet the orthogonal 2D polyomino on its stair part. Now if a diagonal polyomino belongs to three diagonals, then it also belong to the four diagonals (see figure 3(a)).

**Polyominoes along two diagonals** The generic form of polyominoes on two diagonals can be described as two 2D corner-polyominoes sharing their corner cell which also belongs to a full pilar perpendicular to the corner-polyominoes. Since we already know the generating function for 2D corner-polyominoes, it is easy to deduce the generating function for diagonal polyominoes belonging to two and three diagonals.
<figure><img src="image_3.png" /><figcaption>**Fig. 3:** Diagonal polyominoes on more than one diagonal</figcaption></figure>

**Proposition 3** The number $2\mathrm{diag}_z(b, k, h)$ of 3D diagonal polyominoes belonging to the two diagonals perpendicular to the $xy$ face of a prism such that the projection of these two diagonals has a vertex in the upper left corner of the face of size $b \times k$ has the following generating function

$$2\mathrm{diag}_z(x, y, z) = \sum_{b,k,h \ge 1} 2\mathrm{diag}_z(b, k, h)x^b y^k z^h = \frac{1}{xy} \left( \frac{2xy}{(1-x-y)} - \frac{xy}{(1-x)(1-y)} \right)^2 \frac{z}{(1-z)^2}$$

**Proof:** This is immediate from equation (2) and the fact that these polyominoes have the geometric structure $2D \text{ corner} \times (2D \text{ corner} - \text{ corner cell}) \times \text{pilar.}$ □

**3D crosses** Next we need the generating function $3\mathrm{cross}(x, y, z)$ of 3D crosses which are the 3D minimal polyominoes made only of pilars, at least three, meeting on one common cell $c$ (see figure 3(a)). Observe that for a prism of size $b \times k \times h$ with $b, k, h \ge 2$, there are $bkh$ cross polyominoes inscribed in that prism and only one if any two of these three parameters equals one. We will only consider crosses in a box of size at least $2 \times 2 \times 2$. We thus have:

$$3\mathrm{cross}(x, y, z) = \sum_{b,k,h \ge 2} bkhx^b y^k z^h = \frac{x^2(2-x)y^2(2-y)z^2(2-z)}{(1-x)^2(1-y)^2(1-z)^2}$$

**Proposition 4** The generating function $\mathrm{Diag}(x, y, z)$ of the total number of diagonal polyominoes is the following

$$\mathrm{Diag}(x, y, z) = 4 \cdot 1\mathrm{Diag}(x, y, z) - 2(2\mathrm{diag}_z(x, y, z) + 2\mathrm{diag}_y(x, y, z) + 2\mathrm{diag}_x(x, y, z)) \\ + 3 \cdot 3\mathrm{cross}(x, y, z) \quad (7)$$

**Proof:** In order to count all 3D diagonal polyominoes, we use inclusion-exclusion. Here are the steps: 1- Count polyominoes along one diagonal and multiply by four. 2- The polyominoes that belong to two diagonals or more were counted twice or more so for each pair of 3D diagonals, remove the polyominoes belonging to those two diagonals. 3- The polyominoes belonging to three diagonals, and thus to four, were counted four times in the first step, removed six times in the second step and so must be added three times to be counted once. Notice that this inclusion-exclusion argument is not valid for degenerate prisms that have one side of length one and for their corresponding terms in the generating function (7). □
## 3 Non diagonal polyominoes

Does there exists minimal 3D polyominoes that are not diagonals ? The answer is yes and figure 4 shows a sample of these objects. For instance the polyomino in figure 4(a) is not diagonal because it has no corner-polyomino as component. This polyomino can be seen as the juxtaposition of two perpendicular 2D polyominoes each with contact cell that is not a corner cell. This is our definition for the family of non diagonal minimal polyominoes that we call $2D \times 2D$ polyominoes.

### 3.1 $2D \times 2D$ polyominoes

In what follows, we establish the generating function for $2D \times 2D$ polyominoes. For that purpose, we split these polyominoes in three parts, each part corresponding to one color in figure 4(a). The central part, made of green cells with red corners, will be called a skew hook. It consists of three mutually orthogonal segments of cells. The two end segments touch a face of the prism and so are pilars with at least one cell. They touch the middle segment on its end cells. These two end cells are the contact cells of the two other parts (one in blue and one in yellow in figure 4(a)). If we discard the two pilars, each end cell of the middle segment can be seen as the corner cell of a 2D corner-polyominoe. The two 2D corner-polyominoes with their associated pilars are perpendicular and each one goes from one face to its opposite face. Notice that the smallest prism that contains a $2D \times 2D$ polyominoe has size $2 \times 3 \times 3$ and in that case, the polyominoes are made of two perpendicular full pilars that are the discrete version of euclidian skew lines.

We begin with the generating function of skew hooks. This is quite elementary when we consider that each pilar contains at least one green cell and the central segment contains two red end cells but not necessarily green cells. In order to fix ideas, we agree that the yellow 2D polyomino is in the $yz$ plane with $z$ length at least two if we count the red corner cell. The blue 2D polyomino is in the $xy$ plane. If we decide that we do not count the contribution in $x$ and $z$ of the central segment and the contribution in $y$ of the red corner cells. We have the following generating function $SH(x, y, z)$ for skew hooks :

$$SH(x, y, z) = \frac{x}{(1-x)} \times \frac{1}{(1-y)} \times \frac{z}{(1-z)}$$

The yellow 2D corner polyominoes in the $yz$ plane of $z$ height at least 2 and the blue 2D corner polyominoes in the $xy$ plane of $x$ length at least 2 : are obtained from (2):

$$2D_{c,z \ge 2}(y,z) = yz \left( \frac{2}{(1-y-z)} - \frac{2-z}{(1-y)(1-z)} \right), 2D_{c,x \ge 2}(x,y) = xy \left( \frac{2}{(1-x-y)} - \frac{2-x}{(1-x)(1-y)} \right).$$

In order to assemble these three components, observe that if we fix the vertical pilar and the yellow 2D corner, then the horizontal green pilar may take two directions that determines the direction of the blue 2D polyomino which is equivalent to multiply by two the number of blue 2D corner-polyominoes and remove the 2D crosses which would be counted twice otherwise. We do the same for the yellow 2D corner-polyominoes. Finally, observe that the yellow polyomino could be on the left rather than on the right of the central part which multiplies by two again the number of polyominoes and we obtain the following generating function for $2D \times 2D$ polyominoes with orthogonal planes $xy$ and $yz$.

$$P_{xy \times yz}(x, y, z) = 2 \left( 2 \cdot 2D_{c,x \ge 2}(x, y) - \frac{x^2 y}{(1-x)(1-y)} \right) \cdot SH \cdot \left( 2 \cdot 2D_{c,z \ge 2}(y, z) - \frac{yz^2}{(1-y)(1-z)} \right) \quad (8)$$
<figure><img src="image_4.png" /><figcaption>Fig. 4: Non diagonal Polyominoes</figcaption></figure>

Finally, observing that two pairs of orthogonal planes determine two disjoint sets of $2D \times 2D$ polyominoes, we obtain the generating function $P_{2D \times 2D}(x, y, z)$ for the total number of non diagonal $2D \times 2D$ polyominoes by adding the three generating functions corresponding to each pair of orthogonal planes:

$$P_{2D \times 2D}(x, y, z) = P_{xy \times yz} + P_{xy \times xz} + P_{xz \times yz} \quad (9)$$

## 3.2 Skew cross polyominoes

We define our second family of non diagonal polyominoes as follow: a skew cross polyomino starts with a central cell c of degree three which is the corner cell of three 2D corner-polyominoes mutually perpendicular. We partition this family in two types. **Type a)** The cell c has two parallel contact faces. **Type b)** The three contact faces of the central cell c are incident to a vertex of c. These two families are illustrated in figures 4(d) and 4(e).

**Type a)** We start by establishing the generating function for each of the three 2D corner-polyominoes needed to obtain a skew cross polyomino of type a). To fix the ideas, suppose that the three contact faces of the cell c have already been chosen and that the 2D corner-polyomino red and green is in the yz plane, the yellow part is in the xz plane and the blue part is in the xy plane as illustrated in figure 4(d). We have the choice between the red central cell c and the cell in contact with it as the corner cell of the 2D corner-polyomino. We choose the cell in contact with c. For the 2D corner-polyomino in the yz plane, the z length must be at least 2 and the generating function is

$$P_{c,z \ge 2}(y,z) = yz \left( \frac{2}{(1-y-z)} - \frac{1}{(1-y)(1-z)} - \frac{1}{(1-y)} \right) \quad (10)$$

Similarly we obtain generating functions $P_{c,x \ge 2}(x, y)$, $P_{c,z \ge 2}(x, z)$ for the 2D corner-polyominoes in the xy and xz planes. The product of these three series gives the generating function of skew cross polyominoes of type a with preselected faces of the central cell provided we adjust with the fact that the z length of the cell c was counted twice and its y length was not counted. Now once the faces of c are chosen, there is some freedom for the direction of the 2D corner-polyominoes. Indeed, if we choose first one of the two directions of the corner-polyomino coming from the face between opposite faces, then we still have to choose between two directions for another 2D corner-polyomino. For two faces in the xz plane, we have two choices for a face yz. Thus the generating function $SC_{a1}(x, y, z)$ of skew crosses of
type a when two faces in plane xz and one face in the plane yz are chosen is :

$$SC_{a1}(x, y, z) = \frac{4y}{z} P_{c,z \ge 2}(y, z) P_{c,x \ge 2}(x, y) P_{c,z \ge 2}(x, z)$$

There are 12 triplets of faces of type a on a cell c, we sum six generating functions similar to equation (11) and obtain the generating function $SC_a(x, y, z)$ for skew crosses of type a which simplifies to:

$$SC_a(x, y, z) = \frac{-16x^3y^3z^3((1-x+y)(1-x+z) + (1-y+x)(1-y+z) + (1-z+x)(1-z+y))}{(1-x)^2(1-y)^2(1-z)^2(1-y-z)(1-x-y)(1-x-z)}$$

**Type b** To establish the generating function of skew crosses of type b, we choose three faces of the cell c incident to one vertex of c. We choose each cell in contact with a face of c to be the corner cell of a 2D corner-polyomino. There are two possibilities once the three corner cells are chosen. Here is the generating function for a given set of three faces corresponding to one vertex of c:

$$P_{c,z \ge 2}(x, z) \times P_{c,x \ge 2}(x, y) \times P_{c,y \ge 2}(y, z) + P_{c,y \ge 2}(x, y) \times P_{c,z \ge 2}(y, z) \times P_{c,x \ge 2}(x, z)$$

There are 8 sets of three faces of c incident to one vertex and for each set, we obtain the same generating function which means that the generating function for skew crosses of type b is the following:

$$SC_b(x, y, z) = 8(P_{c,z \ge 2}(x, z) \times P_{c,x \ge 2}(x, y) \times P_{c,y \ge 2}(y, z) + P_{c,y \ge 2}(x, y) \times P_{c,z \ge 2}(y, z) \times P_{c,x \ge 2}(x, z))$$

The generating function for all skew crosses $SC(x, y, z)$ is the sum of the generating functions for types a and b so that we obtain

$$SC(x, y, z) = \frac{64x^3y^3z^3}{(1-x-y)(1-x-z)(1-y-z)(1-x)^2(1-y)^2(1-z)^2} \quad (11)$$

# 4 Main result

So far we have established three disjoint classes of 3D polyominoes. We claim that the union of these three classes forms the whole set of 3D inscribed polyominoes with minimal volume.

**Theorem 3** The total number $p_{3D,min}(b, k, h)$ of polyominoes inscribed in a $b \times k \times h$ rectangular prism and minimal volume $b + k + h - 2$ is the sum of diagonal polyominoes and non diagonal polyominoes of type $2D \times 2D$ and skew crosses:

$$p_{3D,min}(b, k, h) = \mathrm{diag}(b, k, h) + p_{2D \times 2D}(b, k, h) + sc(b, k, h).$$

**Proof:** In order to prove this result, we introduce a second classification of 3D polyominoes and we show that every set of polyominoes forming this classification belongs to one of our three families of polyominoes.

Consider the orthogonal projection $\Pi(P)$ of an inscribed 3D polyomino $P$ on the upper face of the prism. $\Pi(P)$ is a 2D inscribed polyomino of minimal area and therefore possesses the geometric structure *hook-stair-hook* of minimal 2D polyominoes. Two cells of the 3D polyomino play a special role in our classification. We call them *contact cells* and define them as follow. For every polyomino $P \in$
$P_{3D,min}(b, k, h)$ there is a unique 3D stair connecting the lower and upper faces of the prism which forms a non decreasing path from floor to ceiling. The two contact cells $c_1, c_2$ are respectively, the last cell touching the floor and the first cell touching the ceiling in this path. We use the positions of the projections $\Pi(c_1), \Pi(c_2)$ in our classification. If, without loss of generality, we fix a 2D diagonal in the upper face to give a direction to the hook-stair-hook structure, there are ten positions of the pair $\Pi(c_1), \Pi(c_2)$ with respect to the upper hook, each pair giving a class in this classification of $P_{3D,min}(b, k, h)$. The ten positions can be seen in figure 4 where $\Pi(c_1)$ and $\Pi(c_2)$ are black. Observe that these ten cases do not form a complete partition of the set $P \in P_{3D,min}(b, k, h)$ but our goal is to provide a complete set of representatives up to symmetry so that every other case is similar to one of the cases considered.

The remaining part of the proof shows that the polyominoes in each of the 10 cases also belong to one of the three families of polyominoes, namely diagonal, $2D \times 2D$ and skew cross polyominoes.

<figure><img src="image_5.png" /><figcaption>Fig. 5: Classification of the projection of 3D polyominoes on the upper face of the prism</figcaption></figure>

<figure><img src="image_6.png" /></figure>

# 5 Exact formulas

We did not find exact formulas for all the generating functions produced: the exact expressions are not always reducible. For example, here is an exact expression for the number $sc(b, k, h)$ of skew crosses inscribed in a $b \times k \times h$ prism that we could not reduce:

$$sc(b, k, h) = 64 \sum_{i=0}^{b+k-6} \sum_{r=0}^{i} \sum_{j=0}^{b-3-r} \binom{b}{3+r+j} \binom{k}{3+i+j-r} \binom{h}{3+i} \quad b \ge 3, k \ge 3, h \ge 3 \quad (12)$$

but if we turn our interest to the number of all minimum inscribed polyominoes of a given volume $n$, we obtain interesting exact formulas and generating functions. In what follows, we obtain exact formulas by setting $x = y = z$ for each of the three families of 3D polyominoes to obtain one for the set $P_{3D,min}(n)$.

$$sc(n-2) = 2^{n+2} (n^2 - 27n + 194) - 8 \left( \frac{n^5}{15} + \frac{11n^3}{3} + 12n^2 + \frac{844n}{15} + 96 \right) \quad (13)$$
$$p_{2D \times 2D}(n-2) = 3 \cdot 2^{n+2}(n-15) + \left( \frac{3}{40}n^6 - \frac{33}{40}n^5 + \frac{65}{8}n^4 - \frac{183}{8}n^3 + \frac{544}{5}n^2 + \frac{147}{10}n + 234 \right) \quad (14)$$

$$diag(n-2) = \frac{121}{48}3^n - 2^n(45n - 411) - \left( \frac{53}{120}n^5 - \frac{15}{8}n^4 + \frac{823}{24}n^3 - 6n^2 + \frac{22711}{60}n + \frac{4995}{16} \right) \quad (15)$$

Adding equations (13), (14), (15), we finally obtain an exact formula for $p_{3D,min}(n)$.

$$P_{3D,min}(x) = \sum_{n} p_{3D,min}(n)x^{n+2} = \frac{x^3(72x^{10} + 36x^9 + 510x^8 - 1117x^7 + 1276x^6 - 1155x^5 + 710x^4 - 293x^3 + 81x^2 - 13x + 1)}{(1-3x)(1-2x)^3(1-x)^7}$$

$$p_{3D,min}(n) = \frac{11^2 \cdot 3^{n+1}}{16} + 2^{n+2}(4n^2 - 125n + 741) + \frac{3n^6}{40} - \frac{9n^5}{10} - \frac{7n^4}{2} - \frac{133n^3}{2} - \frac{1931n^2}{5} - \frac{31727n}{20} - \frac{47739}{16}$$

## Remarks

1. One of the authors (H. Cloutier), wrote two programs to count minimal inscribed 3D polyominoes. One program uses formulas obtained from the projection $\Pi(P)$ of the polyominoes on the ceiling of the prism. We used the datas obtained from these programs to validate our results.

2. An exact formula for $p_{3D,min}(b, k, h)$ is for the moment out of reach but we have produced exact formulas for $p_{3D,min}(b, k, 2)$ and $p_{3D,min}(b, k, 3)$.

3. The diagonal subseries $DP_{3D,min}(t) = \sum_n p_{3D,min}(n, n, n)t^n$ obtained from $P_{3D,min}(x, y, z)$ by setting equals the exponents of $x, y, z$ satisfies a functional equation of degree six with coefficients polynoms in $t$ [6]. But no exact expression for $p_{3D,min}(n, n, n)$ could be found.

## References

[1] M. Bousquet-Mélou, A.J. Guttman *Enumeration of Three-dimensional Convex Polygons*, Annals of Combinatorics, no 7, 27–53, 1997.

[2] C.J. Bowkamp, *Packing a rectangular box with the twelve solid pentominoes*, J. of Combinatorial Theory, no 7, 278–280, 1969.

[3] K. Gong, http://kevingong.com/Polyominoes/Enumeration.html, consulted july 11 2010.

[4] A. Goupil, H. Cloutier, F Nouboud, *Enumeration of inscribed polyominoes*, Discrete Applied Mathematics, no 158, 2010, p. 2014-2023.

[5] S. Golomb, *Checker Boards and Polyominoes*, Amer. Math. Monthly 61, 675–682, 1954.

[6] Guoce Xin, *Personal communication*, August 2010.

[7] P.A. MacMahon, *Combinatory Analysis*, Vols. I and II, Cambridge University Press, Cambridge, 1915-1916, reprinted 1960.