# Enumeration of inscribed polyominos

Alain Goupil¹†, Hugo Cloutier¹ and Fathallah Nouboud¹

¹Département de mathématiques et d'informatique, Université du Québec à Trois-Rivières, 3351 boul des Forges, c.p. 500, Trois-Rivières (QC) Canada

alain.goupil@uqtr.ca, hugo854@yahoo.ca, Fathallah.Nouboud@uqtr.ca

**Abstract.** We introduce a new family of polyominos that are inscribed in a rectangle of given size for which we establish a number of exact formulas and generating functions. In particular, we study polyominos inscribed in a rectangle with minimum area and minimum area plus one. These results are then used for the enumeration of lattice trees inscribed in a rectangle with minimum area plus one.

**Résumé.** Nous introduisons une nouvelle famille de polyominos inscrits dans un rectangle de format donné pour lesquels des formules exactes et des séries génératrices sont présentées. Nous étudions en particulier les polyominos inscrits d'aire minimale et ceux d'aire minimale plus un. Ces résultats sont ensuite utilisés pour l'énumération de polyominos arbres inscrits dans un rectangle d'aire minimum plus un.

**Keywords:** inscribed polyomino, enumeration, rectangle, generating function, lattice tree, minimal area.

## 1 Introduction

S. Golomb introduced polyominos in 1952 [6]. Various families of polyomominos have been defined and investigated since then (see [1], [2], [4], [5] and ref. therein). Algorithms have also been developed for their enumeration (see [7]). But the problem of their enumeration in the general case remains unsolved. In this work, we have developed formulas that, to our knowledge, are counting polyominos of a family not described in the existing literature so we could not connect our work with it.

A polyomino, sometimes called an animal, is a set of unit square cells in the discrete plane $N \times N$ connected by their edges up to translation. We are interested in the number $p(n)$ of polyominos with $n$ cells where $n$ is called the *area* of these polyominos. A polyomino is inscribed in a rectangle $b \times k$ when it is included in the rectangle and each of the four edges of the rectangle is touched by a cell of the polyomino. The minimum number of cells in a polyomino inscribed in a $b \times k$ rectangle has $b + k - 1$ cells and we will denote respectively by $p_{min}(b, k)$ and $p_{min+1}(b, k)$ the number of polyominos that are inscribed in a $b \times k$ rectangle and have minimum area and minimum area plus one. A lattice tree is a polyomino that contains no cycle and we will also be interested with lattice trees inscribed in a rectangle. The main results of this work are the following.

<footnote>†Work supported in part by NSERC</footnote>
**Theorem 1** For integers $b \ge 2, k \ge 2$, the number $p_{min}(b, k)$ of polyominos inscribed in a rectangle $b \times k$ with minimal area $n = b + k - 1$ is given by the formula

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

**Corollary 1** For all integers $n \ge 1$ the number $p_{min}(n)$ of polyominos with $n$ cells inscribed in a rectangle of perimeter $2(n + 1)$ is given by the formula

$$p_{min}(n) = 2^{n+2} - \frac{1}{2}(n^3 - n^2 + 10n + 4)$$

The polyominos in the previous corollary can also be seen as animals occupying a rectangular region of maximal perimeter with respect to their area.

**Theorem 2** The two variables generating function for the number $p_{min}(b, k)$ of polyominos of minimal area inscribed in a rectangle $b \times k$ has the following rational form:

$$\sum_{b,k \ge 1} f_{min}(b,k) x^b y^k = 2 \left( 1 + \frac{xy}{(1-x)(1-y)} \right)^2 \frac{xy}{(1-x-y)} - \left( \frac{xy}{(1-x)^2(1-y)^2} - \frac{xy^2}{(1-y)^2} - \frac{x^2y}{(1-x)^2} \right)$$

**Theorem 3** For all integers $b, k \ge 1$, the number $p_{min+1}(b, k)$ of polyominos inscribed in a rectangle $b \times k$ that have minimum area plus one is

$$p_{min+1}(b, k) = \begin{cases} 0 & \text{if } b=1 \text{ or } k=1 \\ 1 & \text{if } b=k=2 \\ 4b^2 - 16b + 18 & \text{if } k=2 \text{ and } b>2 \\ \begin{aligned} & 8(b+k-22)\binom{b+k-4}{b-2} + \frac{8(2k^2+2kb+b-13k+13)}{(k-2)}\binom{b+k-4}{b-1} \\ & + \frac{8(2b^2+2kb+k-13b+13)}{(b-2)}\binom{b+k-4}{k-1} + 48\binom{b+k-2}{b-1} \\ & - \frac{4}{3}(b^3+k^3) - 12(b^2k+bk^2) + 16(b^2+k^2) \\ & + 72bk - \frac{266}{3}(b+k) + 120 \end{aligned} & \text{if } b \ge 3 \text{ and } k \ge 3 \end{cases}$$

**Corollary 2** For all integers $n \ge 5$, the number $p_{min+1}(n)$ of polyominos with $n$ cells inscribed in a rectangle of perimeter $2n$ is

$$p_{min+1}(n) = 2^{n-1}(5n-6) - \frac{2}{3}(4n^4 - 44n^3 + 215n^2 - 451n + 318)$$

A consequence of theorem 3 and corollary 2 is to obtain exact formulas for corresponding sets of lattice trees inscribed in a rectangle.

It is clear that any general polyomino is always inscribed in a rectangle so that the set $Po(n)$ of polyominos with area $n$ can be partitioned into classes given by the dimensions $b \times k$ of the circonscribed rectangles. Our approach in counting inscribed polyominos thus constitute a fair strategy to attack the well known problem of counting the total number $po(n) = card(Po(n))$ of polyominos of area $n$.
**Notations.** As a general rule we will use capital letters for sets and corresponding small letters for their cardinalities. We will introduce specific notations as they are needed.

## 2 Proofs of the formulas

Proof of theorem 1. We begin with two geometric observations on inscribed polyominos with minimal area. 1- All inscribed polyominos with minimal area are oriented along one of the two diagonals of the $b \times k$ rectangle noting that polyominos with a cross shape (figure (1 d)) are the only polyominos with minimal area that can be seen as oriented along both diagonals. 2- Minimal area polyominos all have a structure in three parts: one hook, possibly reduced to a unique cell, on each end of the diagonal connected on their corner by a stair polyomino in the direction of the diagonal as shown in figure 1 c). A stair polyomino (figure (1 b)) along one diagonal, going say from north-west to south-east $\setminus$ is a path allowed only two directions for adjacent cells: east $\to$ and south $\downarrow$.

<figure><img src="image_1.png" /><figcaption>**Fig. 1:** Inscribed minimal polyominos</figcaption></figure>

The geometric triple-structure of polyominos with minimal area appearing in figure 1 c) can also be given a biological interpretation. Animals with n cells that need to touch the edges of a rectangle of maximal perimeter must have this geometric triple-structure and shape.

We have produced two proofs of theorem 1. Each proof consists in a case study of the set of polyominos of minimal area. The first proof uses the triple-structure hook-stair-hook of minimal polyominos and the second proof is a dynamic construction of the polyominos beginning with the fundamental hook (figure 1 a)) and moving the square cells horizontally or vertically to form a new inscribed polyomino. We present here only the first proof.

Let $P_{min,\setminus}(b, k)$ be the set of polyominos of minimal area inscribed in a rectangle $b \times k$ along the diagonal from north-west to south-east. Denote by $p_{min,\setminus}(b, k)$ the cardinality of $P_{min,\setminus}(b, k)$. Let $P_{min,/(b, k)}$ and $p_{min,/(b, k)}$ be similarly defined for the other diagonal. Since there is clearly a bijection between the two sets $P_{min,\setminus}(b, k)$ and $P_{min,/(b, k)}$, we need only consider one of the diagonals of the rectangle. The set $P_+(b, k)$ of Cross polyominos satisfies $P_+(b, k) = P_{min,\setminus}(b, k) \cap P_{min,/(b, k)}$, so that we have

$$p_{min}(b, k) = 2p_{min,\setminus}(b, k) - p_+(b, k) \quad (1)$$

Let $P_{min,(i,j)}(b, k)$ be the set of polyominos in $P_{min,\setminus}(b, k)$ having the corner cell of their upper left hook in position $(i, j)$ in matrix notation. Thus $p_{min,(1,1)}(b, k)$ is the number of polyominos in $P_{min,\setminus}(b, k)$ that have a cell in the upper left corner of the rectangle $b \times k$. Let us count these polyominos. First observe
that the cell in position (1, 1) must be in one of three situations: a) it is connected to a cell on its right with no cell below. b) it is connected to a cell below with no cell on the right. c) It has a cell on the right and a cell below. In the first two cases, if we remove the cell (1, 1) we obtain polyominos with minimal areas inscribed in a smaller rectangle. There is only one polyomino with minimal area in the third case. Thus we obtain the recurrence

$$p_{min,(1,1)}(b,k) = p_{min,(1,1)}(b,k-1) + p_{min,(1,1)}(b-1,k) + 1 \quad \forall b, k \ge 1 \quad (2)$$

with the initial conditions $p_{min,(1,1)}(b, 0) = p_{min,(1,1)}(0, k) = 0$. There is also an exact expression for $p_{min,(1,1)}(b, k)$. The key observation is the well known fact that the number of stair polyominos inscribed in a rectangle with cells in each corner of a diagonal is given by a binomial coefficient. Let $P_{stair}(b, k)$ be the set of stair polyominos in $P_{min,\setminus}(b, k)$ with end cells in each end of the main diagonal of the rectangle $b \times k$. Then

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

Polyominos in $P_{min,(1,1)}(b, k)$ are in bijective correspondance with polyominos in $(\cup_{i<b,j<k} P_{stair}(i, j)) \cup P_{stair}(b, k)$ so that using basic binomial identities we obtain

$$p_{min,(1,1)}(b,k) = \sum_{i=1}^{b-1} \sum_{j=1}^{k-1} \binom{i+j-2}{i-1} + \binom{b+k-2}{b-1} = 2\binom{b+k-2}{b-1} - 1 \quad (4)$$

Moreover it is also immediate that

$$p_{min,(i,j)}(b,k) = p_{min,(1,1)}(b-i+1,k-j+1) \quad (5)$$

so that by equation (4) we have

$$p_{min,(i,j)}(b,k) = 2\binom{b+k-i-j}{b-i} - 1. \quad (6)$$

Since $p_+(b, k) = bk$ and

$$p_{min,\setminus}(b,k) = p_{min,(1,1)}(b,k) + \sum_{i=2}^{b} \sum_{j=2}^{k} p_{min,(i,j)}(b,k), \quad (7)$$

using (1) we obtain

$$p_{min}(b,k) = 2 \left( p_{min,(1,1)}(b,k) + \sum_{i=2}^{b} \sum_{j=2}^{k} p_{min,(i,j)}(b,k) \right) - bk, \quad (8)$$

Now using (8) and (6) we obtain an exact expression for $p_{min}(b, k)$:

$$\begin{align}
p_{min}(b,k) &= 2 \left( 2 \binom{b+k-2}{b-1} - 1 + \sum_{i=2}^{b} \sum_{j=2}^{k} \left( 2 \binom{b+k-i-j}{b-i} - 1 \right) \right) - bk \nonumber \\
&= 8 \binom{b+k-2}{b-1} - 6 - 2(b-1)(k-1) - bk \quad \forall b, k \ge 1. \tag{9}
\end{align}$$

which proves theorem 1.

◇
**Proof of corollary 1.** Polyominos with minimal area inscribed in a rectangle can also be seen as polyominos that are maximally stretched. These polyominos occupy a rectangle of maximal perimeter $2n + 2$ when their area is $n$. If we sum maximally stretched polyominos over all rectangles of perimeter $2n + 2$, we obtain the number $p_{min}(n)$ of maximally stretched polyominos:

$$ 
\begin{aligned}
p_{min}(n) &= \sum_{b=1}^{n} p_{min}(b, k) = 2 + \sum_{b=2}^{n-1} \left( 8 \binom{b+k-2}{b-1} - 6 - 2(b-1)(k-1) - bk \right) \quad (10) \\
&= 2^{n+2} - \frac{1}{2}(n^3 - n^2 + 10n + 4)
\end{aligned}
$$

which proves corollary 1. Observe that we have computed separately the cases $b = 1$ and $b = n$ in equation (10) ◇

$$ \begin{array}{c|cccccccccc}
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
p_{min}(n) & 1 & 2 & 6 & 18 & 51 & 134 & 328 & 758 & 1677 & 3594
\end{array} $$

<caption>**Tab. 1:** Numbers $p_{min}(n)$ of maximally stretched polyominos of area $n$</caption>

**Proof of theorem 2.** We construct the rational form of the generating function $\sum_{b,k \ge 1} f_{min,\setminus}(b,k)x^b y^k$ from its triple-structure *hook - stair - hook* described before and the multiplication principle.

Since there is at most one hook in the upper left corner of the rectangle having its corner in position $(i, j)$ and because we choose not to count the corner cell, the generating function for hooks with corner in position $(i, j)$ is

$$ 1 + \sum_{i,j \ge 2} x^{i-1} y^{j-1} = 1 + \frac{xy}{(1-x)(1-y)} \quad (11) $$

Recall that the number of stairs from the upper left corner of a rectangle to the cell $(i, j)$ is $\binom{i+j-2}{i-1}$ so that the generating function for stair polyominos is

$$ 
\begin{aligned}
\sum_{i,j \ge 1} \binom{i+j-2}{i-1} x^i y^j &= xy \sum_{i,j \ge 1} \binom{i+j-2}{i-1} x^{i-1} y^{j-1} = xy \sum_{k \ge 0} (x+y)^k \\
&= \frac{xy}{1-x-y} \qquad (12)
\end{aligned}
$$

Now applying the multiplication principle and equations (11) and (12) we obtain

$$ \sum_{b,k \ge 1} f_{min,\setminus}(b,k) x^b y^k = \left(1 + \frac{xy}{(1-x)(1-y)}\right)^2 \frac{xy}{(1-x-y)} \quad (13) $$

Finally recalling equation 1 we deduce theorem 2 when we agree that the generating function for crosses is

$$ \sum_{b,k \ge 1} f_{+}(b,k) x^b y^k = \sum_{k \ge 1} xy^k + \sum_{b \ge 2} x^b y^k + \sum_{b,k \ge 2} bkx^b y^k = \frac{xy}{(1-x)^2(1-y)^2} - \frac{xy^2}{(1-y)^2} - \frac{x^2 y}{(1-x)^2} $$
**Proof of theorem 3.** The proof of theorem 3 is also a case study, with more cases though than in the proof of theorem 1. We will need $2 \times t$ bench polyominos that we define as polyominos of area $t + 2$ inscribed in a $2 \times t$ rectangle, $t \ge 2$, with one full row, or column, of cells plus the two cells at each end of the other row as shown in figure 2 a). We will use the following triple-structure description of polyominos

<figure><img src="image_2.png" /><figcaption>Fig. 2: Bench polyominos</figcaption></figure>

of area $min + 1$ inscribed in a rectangle.

**Facts.**
a) A polyomino of area $min + 1$ inscribed in a rectangle contains exactly one bench polyomino in one of the four possible positions of figure 2 a).
b) Moreover there is exactly two ways to complete a fixed bench into a polyomino of area $min + 1$ along one diagonal of the $b \times k$ rectangle. First, a polyomino of minimal area is attached to a corner of the bench (figure 2 b)) and if it is a hook, it may have its corner cell on any cell of the $2 \times t$ circumscribed rectangle (figure 2 c)), provided the connectivity condition is satisfied. Second, a polyomino of minimal area is attached on the opposite corner and if it is a hook, it may have its corner on any cell of the $2 \times t$ circumscribed rectangle up to connectivity.

c) Starting on the north-west corner and moving clockwise, let $c_1, c_2, c_3$ and $c_4$ be the four corner cells of a bench polyomino $B$ included in a $b \times k$ rectangle. Let $f_1, f_2, f_3, f_4$ be the number of polyominos inscribed in the respective rectangles determined by the diagonals from the northwest corner of the $b \times k$ rectangle to the northwest corner $c_1 \in B$ and so on for the other three rectangles as in figure 3.

<figure><img src="image_3.png" /><figcaption>Fig. 3: A polyomino of area $min + 1$ constructed from a bench polyomino</figcaption></figure>

The number $p(B)$ of polyominos of area $min + 1$ inscribed in a $b \times k$ rectangle and containing the bench polyomino $B$ is given by the formula

$$p(B) = f_1 \cdot f_3 + f_2 \cdot f_4 - 8t \quad (14)$$

**Case 1. The bench is in a corner.** Let us start by considering the case where a bench is in one corner of the rectangle.
**Proposition 1** For integers $t \ge 2$ let $p_{t,1}(b, k)$, resp. $p_{t,2}(b, k)$, be the number of polyominos in $P_{min+1}(b, k)$ containing a $2 \times t$ bench in the northwest corner of the rectangle with the seating part (figure 4 a), resp. the leg part (figure 4 b), upward. Then we have

$$p_{t,1}(b, k) = 2\binom{b+k-t-2}{b-2} + 2 \qquad (15)$$

$$p_{t,2}(b, k) = 2\binom{b+k-t-2}{b-2} + 2(t-1) \qquad (16)$$

**Proof:** We have to observe that once a bench is placed in a corner of the rectangle, we may complete it into a polyomino of area $min + 1$ either by adding a polyomino of minimal area inscribed in the sub-rectangle with corners given by the southeast corner of the bench and the southeast corner of the rectangle or by adding a hook as shown in figure 4. In the case where the legs of the bench are upwards, the corner of the hook, sometimes absent, is any of the $2t$ cells of the rectangle containing the bench. In the case where the legs of the bench are downwards, there are 4 possible hooks, one of which is already counted. Formulas (15) and (16) then follow from equation (4). $\square$

<figure><img src="image_4.png" /><figcaption>**Fig. 4:** Case 1. A bench in a corner</figcaption></figure>

**Corollary 3** For integers $b, k \ge 3$, the number $g_1(b, k)$ of polyominos of area $min + 1$ inscribed in a $b \times k$ rectangle with a bench polyomino $2 \times t$ in any corner of the rectangle is given by the formula

$$g_1(b, k) = (4 \sum_{t=3}^{k-1} p_{t,1}(b, k) + 4) + (4 \sum_{t=3}^{k-1} p_{t,2}(b, k) + 2k) \qquad (17)$$

$$+(4 \sum_{t=3}^{b-1} p_{t,1}(k, b) + 4) + (4 \sum_{t=3}^{b-1} p_{t,2}(k, b) + 2b),$$

$$= 16 \left( \binom{b+k-4}{b-1} + \binom{b+k-4}{k-1} \right) + 2k(2k-1) + 2b(2b-1) - 72 \qquad (18)$$

**Proof:** This is a consequence of proposition 1 and of a careful study of the particular cases involved. In each corner of the rectangle there are up to four benches to consider; the sums in formula (17) cannot be taken up to $t=k$ because there are less cases to consider. Also symmetry in $b, k$ have been integrated to shorten the expressions. $\square$
<figure><img src="image_5.png" /><figcaption>Fig. 5: The three dispositions of a horizontal bench along one side</figcaption></figure>

**Case 2. The bench touches one side of the rectangle and is not in a corner.** There are three ways to put a horizontal bench on one side of a $b \times k$ rectangle as shown in figure 5.

**Proposition 2** Let $g_{2-horiz}(b, k)$ be the number of polyominos of area $min + 1$ inscribed in a $b \times k$ rectangle with a horizontal bench polyomino of length $t \ge 3$ along one of the sides without being in a corner of the $b \times k$ rectangle. We have

$$ 
\begin{aligned}
g_{2-horiz}(b, k) &= 2 \left[ \sum_{t=3}^{k-2} \sum_{j=2}^{k-t} 2p_{t,1}(b, k-j+1) + 2p_{t,1}(b, j+t-1) - 8 \right] + \\
&\quad 2 \left[ \sum_{t=3}^{k-2} \sum_{j=2}^{k-t} 2p_{t,2}(b, k-j+1) + 2p_{t,2}(b, j+t-1) - 4t \right] + \\
&\quad 4 \left[ \sum_{t=3}^{k-1} \sum_{i=2}^{b-2} tp_{t,1}(b-i+1, k) + 2p_{t,2}(i+1, k) - 4t \right] + 4k(b-3) \\
&= 8 \left[ -2k + 6 + 2 \binom{b+k-4}{b} \right] + 2 \left[ 8 \binom{b+k-4}{b} + \frac{2}{3}(k-3)(k^2-6k-4) \right] \\
&\quad + 2 \left[ \frac{2(5b+k-7)}{k-2} \binom{b+k-4}{b-1} - 7bk + 2b + bk^2 - 4k^2 + 14k + 2 \right] + 4k(b-3)
\end{aligned}
$$

**Proof:** Omitted. $\square$

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

**Corollary 4** Let $g_2(b, k)$ be the number of polyominos inscribed in a $b \times k$ rectangle and area $min + 1$ containing a bench polyomino $2 \times t$, $t \ge 3$ touching one of the sides without being in a corner of the $b \times k$ rectangle. We have

$$ 
\begin{aligned}
g_2(b, k) &= g_{2-horiz}(b, k) + g_{2-horiz}(k, b) \\
&= 32 \left( \binom{b+k-4}{b} + \binom{b+k-4}{k} \right) + \\
&\quad 8 \left( \frac{5k+b-7}{b-2} \binom{b+k-4}{k-1} + \frac{5b+k-7}{k-2} \binom{b+k-4}{b-1} \right) + \\
&\quad \frac{4}{3}(b^3+k^3) - 28(k^2+b^2) - 48bk + \frac{164}{3}(b+k) + 4(bk^2+b^2k) + 144
\end{aligned}
$$
**Proof:** The first equality partitions polyominos into polyominos containing horizontal and vertical benches and the second equality is obtained from proposition 2. □

**Case 3. The bench touches no side of the rectangle.** Let $g_{3-horiz}(b, k)$ and $g_{3-vert}(b, k)$ be the number of polyominos inscribed in a $b \times k$ rectangle and area $min+1$ containing a $2 \times t$, $t \ge 3$ horizontal and vertical bench polyomino respectively that touches no side of the rectangle.

**Proposition 3 We have**

$$
\begin{align*}
g_{3-horiz}(b, k) &= 2 \sum_{t=3}^{k-2} \sum_{i=2}^{b-2} \sum_{j=2}^{k-t} p_{t,1}(i+1, k-j+1) p_{t,2}(b-i+1, j+t-1) + \\
&\qquad p_{t,1}(i+1, j+t-1) p_{t,2}(b-i+1, k-j+1) - 8t \\
&= 2 \sum_{t=3}^{k-2} \sum_{i=2}^{b-2} \sum_{j=2}^{k-t} \left( 2 \binom{i+k-j-t}{i-1} + 2 \right) \left( 2 \binom{b+j-i-2}{j-1} + 2(t-1) \right) + \\
&\qquad 2 \sum_{t=3}^{k-2} \sum_{i=2}^{b-2} \sum_{j=2}^{k-t} \left( 2 \binom{i+j-2}{i-1} + 2 \right) \left( 2 \binom{b+k-j-i-t}{b-i-1} + 2(t-1) - 8t \right) \\
&= 64 kb - \frac{352}{3} k - \frac{8}{3} k^3 + 40k^2 - 32(b-1) - 16k^2b + 16 (k-4) \binom{b+k-4}{b-2} + \\
&\qquad \frac{16b(k^2-5k+8)}{(b+k-3)} \binom{b+k-3}{k-2} - 32 \binom{b+k-4}{k-4}
\end{align*}
$$

**Proof:** As before, we surround the bench with rectangles that reduce our enumeration to case 1 using inclusion-exclusion for two sets. The four surrounding rectangles are arranged in pairs that allow the completion of polyominos along one of the diagonals of the rectangle as shown in figure 6. This gives the first equality of proposition 3. Then we use equations (15) and (16) to obtain the second binomial expression which we reduce to the third expression using standard binomial identities. □

<figure><img src="image_7.png" /><figcaption>**Fig. 6:** Decompositions of a polyomino with an inner horizontal bench</figcaption></figure>

Now to complete our count for polyominos in case 3, observe that $g_{3-vert}(b, k) = g_{3-horiz}(k, b)$.
**Corollary 5** The number $g_3(b, k)$ of polyominos inscribed in a rectangle $b \times k$ of area $min+1$ containing a bench polyomino of length $t \ge 3$ touching no side of the rectangle is given by

$$ 
\begin{aligned}
g_3(b, k) &= g_{3-horiz}(b, k) + g_{3-horiz}(k, b) \\
&= \frac{8}{3} [24 - 6(b^2k + bk^2) + 48bk - 56(b + k) + 15(b^2 + k^2) - (b^3 + k^3) \\
&\quad -12 \left( \binom{b+k-4}{b} + \binom{b+k-4}{k} \right) + 6(b+k-6) \left( \binom{b+k-4}{b-1} + \binom{b+k-4}{k-1} \right) \\
&\quad -60 \binom{b+k-4}{b-2} + 18 \binom{b+k-2}{b-1} ]
\end{aligned}
$$

**Proof:** This is immediate from proposition 3. $\square$

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

One ingredient is missing to obtain a formula for the number $f_{min+1}(b, k)$. We have to analyse separately the case where the bench has format $2 \times 2$ because it contains more symmetries than the other benches and the formulas are not special cases of the formulas for $2 \times t$ benches.

**Case 4.** $2 \times 2$ benches. The cases are similar to the cases for $2 \times t$ benches with $t \ge 3$.

**Proposition 4** a) The number $p_{2 \times 2-\text{corner}}(b, k)$ of polyominos inscribed in a $b \times k$ rectangle and of area $min + 1$ containing a $2 \times 2$ bench in the upper left corner satisfies the formulas

$$ 
\begin{aligned}
p_{2 \times 2-\text{corner}}(b, k) &= p_{\min, (1,1)}(b-1, k-1) + 3 \\
&= \left( 2 \binom{b+k-4}{b-2} - 1 \right) + 3
\end{aligned}
\quad (19) $$

b) The number $p_{2 \times 2-\text{side}}(b, k)$ of polyominos inscribed in a $b \times k$ rectangle of area $min + 1$ containing a $2 \times 2$ bench along one side and not in a corner of the rectangle satisfies the formula

$$ p_{2 \times 2-\text{side}}(b, k) = \begin{cases} 4(b-3) & \text{if } k=2 \text{ and } b \ge 3 \\ 4(k-3) & \text{if } b=2 \text{ and } k \ge 3 \\ 16 \left[ \binom{b+k-4}{k-1} + \binom{b+k-4}{b-1} - 2 \right] & \text{if } k \ge 3 \text{ and } b \ge 3 \end{cases} \quad (20) $$

c) For integers $b \ge 3$ and $k \ge 3$, the number $p_{2 \times 2-\text{center}}(b, k)$ of polyominos inscribed in a rectangle $b \times k$, of area $min + 1$ and containing a $2 \times 2$ bench polyomino that touches no side of the rectangle is given by

$$ p_{2 \times 2-\text{center}}(b, k) = 8 \left[ \binom{b+k-4}{b-3}(k-3) + \binom{b+k-4}{k-3}(b-3) + \binom{b+k-4}{b-2} + b + k - bk + 1 \right] \quad (21) $$

**Proof:** The proof is similar to the proof for benches of length $t \ge 3$ and we will not repeat the arguments. $\square$

<figure><img src="image_9.png" /></figure>
**Corollary 6** For all positive integers $b, k$, the number $p_{2 \times 2}(b, k)$ of polyominos inscribed in a rectangle with area $min + 1$ and containing a $2 \times 2$ bench is given by the formula

$$p_{2 \times 2}(b, k) = \begin{cases} 0 & \text{if } k = 1 \text{ or } b = 1 \\ 1 & \text{if } k = 2 \text{ and } b = 2 \\ 4(b + k - 4) & \text{if } (k = 2 \text{ and } b > 2) \text{ or } (k > 2 \text{ and } b > 2) \\ 8 \left[ \binom{b+k-4}{b-2} + 2 \binom{b+k-4}{b-1} + 2 \binom{b+k-4}{k-1} - 3 \right] & \text{if } (k = 3 \text{ and } b \ge 3) \text{ or } (k \ge 3 \text{ and } b = 3) \\ 8 \left[ \binom{b+k-4}{b-2} + 1 \right] (b+k-2) - bk & \text{if } k \ge 4 \text{ and } b \ge 4 \end{cases}$$

**Proof:** The first three cases are immediate and the last two cases are consequences of proposition 4. □

We are now ready to complete the proof of theorem 3 which is an immediate consequence of the identity

$$p_{min+1}(b, k) = g_{1}(b, k) + g_{2}(b, k) + g_{3}(b, k) + p_{2 \times 2}(b, k)$$

and of corollaries 3, 4, 5 and 6.

**Proof of corollary 2.** This is a consequence of theorem 3 and the identity

$$p_{min+1}(n) = \sum_{b=2}^{n-2} p_{min+1}(b, n-b)$$

<table><caption>**Tab. 2:** Number $p_{min+1}(n)$ of polyominos of area $n$ inscribed in a rectangle of perimeter $2n$</caption><tr><td>n</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td></tr><tr><td>p<sub>min+1</sub>(n)</td><td>1</td><td>12</td><td>80</td><td>384</td><td>1468</td><td>4756</td><td>13656</td><td>35982</td><td>88740</td><td>209420</td></tr></table>

## 3 Applications

We observe two consequences of the formulas developed in the previous section. First, it is possible to count the number $\ell_{min+1}(b, k)$ of lattice animals inscribed in a $b \times k$ rectangle with area $min + 1$ because

$$\ell_{min+1}(b, k) = p_{min+1}(b, k) - p_{2 \times 2}(b, k). \qquad (22)$$

**Proposition 5** For positive integers $b, k$, the number $\ell_{min+1}(b, k)$ of lattice trees inscribed in a rectangle $b \times k$ and of area $min + 1$ is given by the formula

$$\ell_{min+1}(b, k) = \begin{cases} 0 & \text{if } k \le 2 \text{ and } b \le 2 \\ 4b^2 - 20b + 26 & \text{if } (k = 2 \text{ and } b > 2) \\ & \text{or } (k > 2 \text{ and } b > 2) \\ \frac{8(b + k - 23) \binom{b+k-4}{b-2} + \frac{8(2k^2+2kb+b-15k+17)}{k-2} \binom{b+k-4}{b-1}}{\frac{8(2b^2+2kb+k-15b+17)}{b-2} \binom{b+k-4}{k-1} + 48 \binom{b+k-2}{b-1} - \frac{4}{3}(b^3+k^3)} & \text{if } (k = 3 \text{ and } b \ge 3) \\ -12(b^2k + bk^2) + 16(b^2 + k^2) + 72bk - \frac{266}{3}(b+k) + 144, & \text{or } (k \ge 3 \text{ and } b = 3) \\ -160 \binom{b+k-4}{b-2} + \frac{8(2k^2+2kb+b-13k+13)}{k-2} \binom{b+k-4}{b-1} + 136 \\ + \frac{8(2b^2+2kb+k-13b+13)}{b-2} \binom{b+k-4}{k-1} + 48 \binom{b+k-2}{b-1} + 80bk \\ - \frac{4}{3}(b^3+k^3) - 12(b^2k + bk^2) + 16(b^2 + k^2) - \frac{290}{3}(b+k), & \text{if } k \ge 4 \text{ and } b \ge 4 \end{cases}$$
**Proof:** This is an immediate consequence of equation (22), theorem 3 and corollary 6.

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

**Corollary 7** For all integers $n \ge 5$ the number $\ell_{min+1}(n)$ of lattice trees of area $n$ inscribed in a rectangle of perimeter $2n$ is given by the formula

$$ \ell_{min+1}(n) = 2^{n+1}(n-1) - \frac{2}{3}(4n^4 - 46n^3 + 227n^2 - 473n + 318) \quad (23) $$

**Proof:** This is a consequence of proposition 5 and the equation

$$ \ell_{min+1}(n) = \sum_{b=2}^{n-2} \ell_{min+1}(b, n-b) $$

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

<table><caption>**Tab. 3:** Number $\ell_{min+1}(n)$ of lattice trees of area $n$ inscribed in a rectangle of perimeter $2n$</caption><thead><tr><th>n</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th></tr></thead><tbody><tr><th>ℓ<sub>min+1</sub>(n)</th><td>0</td><td>4</td><td>40</td><td>232</td><td>988</td><td>3420</td><td>10240</td><td>27680</td><td>69588</td><td>166132</td></tr></tbody></table>

**Remark.** All the formulas described in this paper have been verified numerically with independent computer programs that can construct and count the relevant polyominos.

## References

[1] E. Barcucci, A. Frosini, S Rinaldi; *On directed-convex polyominoes in a rectangle*, Discrete Mathematics, 298:62–78, 2005.

[2] M. Bousquet-Mélou; *Codage des polyominos convexes et équations pour l'énumération suivant l'aire*, Discrete Applied Mathematics, 48, 21–43, 1994.

[3] S. Brlek, G. Labelle, A. Lacasse; *Algorithms for polyominoes based on the discrete Green theorem*, Discrete Applied Mathematics, 147, 187–205, 2005.

[4] E. Deutsch; *Enumerating symmetric directed convex polyominoes*, Discrete Mathematics, 280, 225–231, 2004.

[5] J.P. Dubemard, I. Dutour, *Enumeration de polyominos convexes dirigés*, Discrete Mathematics, 157,79–90, 1996.

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

[7] I. Jensen, *Enumerations of lattice animals and trees*, Journal of Statistical Physics. 102 no 3-4, 865–881, 2001.