On avoidance of numbered polyomino patterns

Sergey Kitaev, Toufik Mansour^{∗} and Antoine Vella^{∗}

24th June 2003

Abstract

We generalize the concept of pattern avoidance from permutations to numbered polyominoes, and consider specifically the avoidance of the most natural small polyomino patterns in binary matrices (rectangular numbered polyominoes). For all binary right-angled patterns (0/1 labellings of the essentially unique convex two-dimensional polyomino shape with 3 tiles) and all 2 × 2 binary patterns, we deal with the number of m × n binary matrices avoiding the given pattern, as a function of m and n. In the case of 3 tiles, and the all zeros 2 × 2 pattern, we employ direct combinatorial considerations to obtain either explicit closed form formulas or generating functions; in the other cases, we use the transfer matrix method to derive an algorithm which gives, for any fixed m, a closed form formula in n.

1 Introduction and Background

A polyomino is a finite subset of ℤ^{2}. The elements of a polyomino are called tiles. Given an element p ∈ ℤ^{2}, we denote by x_{p}, y_{p} the first and second coordinates of p. A column (row) of a polyomino P is a maximal set of tiles of P all having the same first (respectively, second) coordinate. A line of a polyomino is a row or a column.

Now let G be the graph with ℤ^{2} as vertex set, and with p, q adjacent if and only if |x_{p} − x_{q}| + |y_{p} − y_{q}| = 1. Then G is a self-dual planar graph and a polyomino can be thought of equivalently as a set of vertices of G or a set of faces of a square tessellation of the plane, which is an embedding of G. The latter interpretation gives the intuition behind the choice of the term “polyomino”, in analogy with the word “domino”.

∗Research financed by the EC’s IHRP Programme, within the Research Training Network “Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272.

Given two polyominoes P_{1}, P_{2}, a polyomino isomorphism is a bijection from P_{1} to P_{2} such that, for every p, q ∈ P_{1}, x_{p} < x_{q} ⇔ x_{ϕ(p)} < x_{ϕ(q)} and y_{p} < y_{q} ⇔ y_{ϕ(p)} < y_{ϕ(q)}. The width (height) of a polyomino P is the maximum over all pairs {p, q} ⊆ P of |x_{p} − x_{q}| (respectively |y_{p} − y_{q}| ). The reduction of P is the polyomino which minimizes the width and the height among all polyominoes isomorphic to P in which all tiles have only nonnegative coordinates. A polyomino shape (or simply a shape) is a polyomino which is its own reduction. The set of polyomino shapes constitutes a system of distinct representatives for the set of equivalence classes of isomorphic polyominoes. If the reduction of a polyomino is a certain shape C, we shall also say that P has the shape C. We shall denote shapes by a geometric

depiction of the relative positions of the tiles; for example stands for

the set {(0, 2), (1, 0), (2, 1), (3, 1)}, which is the reduction of, for example, {(−5, 8), (2, 1), (6, 2), (7, 4)}.

A polyomino is connected if the corresponding induced subgraph of G is connected. Connected polyominoes with various restrictions have received much attention in the literature, although they are usually referred to simply as polyominoes or “animals”. The enumeration of connected polyomino shapes seems to be hard. See [4] for an overview of results enumerating small polyomino shapes by “area” (number of tiles) and “perimeter”; one class of connected polyomino shapes which has been well-studied is that of “polygons”, whose boundaries are closed self-avoiding walks.

Note that a shape can be characterized as a polyomino P satisfying the following convexity-type property:

∀ p, q ∈ P, ∀ c, d : x_{p} ≤ c ≤ x_{q}, y_{p} ≤ d ≤ y_{q} ∃ a, b ∈ P : x_{a} = c, y_{b} = d.

In the literature, a polyomino is usually called:

• row-convex if it satisfies the condition:

∀ p, q ∈ P, a ∈ ℤ^{2}, x_{p} ≤ x_{a} ≤ x_{q}, y_{p} = y_{a} = y_{q} ⇒ a ∈ P;

• column-convex if ∀ p, q ∈ P, a ∈ ℤ^{2}, y_{p} ≤ y_{a} ≤ y_{q}, x_{p} = x_{a} = x_{q} ⇒ a ∈ P;

• and convex if it is both row- and column-convex.

Connected convex polyomino shapes seem to be easier to enumerate; in particular, a closed form expression enumerating them by perimeter was given by Delest and Viennot [5]. For connected row-convex polyominoes, it is well-known that the number of polyomino shapes with n tiles satisfies a third-order linear recurrence relation; see, for example, [6].

A polyomino is one-dimensional if it has only one row, or only one column; it is two-dimensional otherwise. Given a non-negative integer n, [n] denotes the set of non-negative integers less than or equal to n; a set of this form is called an interval. A shape is rectangular if it is a cartesian product of intervals; a polyomino is rectangular if its reduction is rectangular.

A numbering ϕ of a set T is a function from T into the set of integers. If the range A of ϕ is finite, there exists a unique order-preserving bijection ψ from A onto the interval of cardinality |A|. The reduction of ϕ is the numbering ϕ ∘ ψ, and a numbering is reduced if it is its own reduction. Also, for any integer k ≥ |A|, ϕ is called a k-numbering. We shall extend our

notation for shapes to numbered shapes in the obvious way: e.g., is a

1-numbering of  , and the reduction of  .

Given a polyomino P, a subset Q ⊆ P is a subpolyomino of P. A numbered polyomino is a polyomino equipped with a numbering. If ϕ is a numbering of P, the subpolyomino Q inherits the numbering ϕ|_{Q}. Given a polyomino Q′ with a numbering ϕ_{Q′}, Q is an occurrence of Q′ in P if there exists a polyomino isomorphism μ from Q to Q′ such that the numberings ϕ|_{Q} and μ∘ϕ_{Q′} have the same reduction; if the two numberings are actually the same, then the occurrence is literal.

Note that numbered rectangular shapes can be thought of as matrices. Thus, for example, the sets^{1} {(0, 2), (1, 0), (3, 1), (4, 1)} and {(1, 2), (2, 0), (3, 1), (5, 1)} are respectively an occurrence and a literal occurrence of the numbered shape in the matrix

1For the sake of consistency with the definition of a polyomino, here we are indexing the entries of a matrix starting with (0, 0) at the bottom left corner and specifying the column in the first coordinate, but in the later sections we shall follow the more common convention of starting with (1, 1) at the upper left corner and specifying the row first.

( \begin{matrix}3 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 3 & 1 \\ 0 & 3 & 1 & 0 & 0 & 0 \end{matrix} ) .

If there are no occurrences of Q′ in P, P is said to avoid Q′.

A numbered polyomino pattern (or simply a pattern) is a polyomino shape equipped with a reduced numbering. We shall usually be concerned with occurrences of patterns in numbered shapes. Given a positive integer k, a shape C and a pattern P, S_{C}^{(k)} denotes the set of k-numberings of C such that the corresponding numbered polyomino avoids the pattern P (the pattern P is understood and not explicitly specified in the notation).

We remark here that given a polyomino pattern, for fixed k there are only finitely many numbered polyomino shapes that are occurrences of the pattern; avoidance of the pattern is equivalent to simultaneous avoidance of literal occurrences of all of these polyomino shapes.

The analysis of avoidance of one-dimensional polyomino patterns can easily be reduced to that of avoidance of the pattern in each row (column) of the given shape, and thus to the study of usual classical patterns, about which a wealth of articles have been published. Hence in this paper we do not attempt to deal with this case, and we assume that all patterns are twodimensional. With this restriction, if the shape C under consideration is a line of n tiles, then |S_{C}^{(k)}| is just k^{n}. Thus, we may also assume that the shapes under consideration are themselves two-dimensional.

In this paper, we shall assume that k = 2 and only examine avoidance of polyomino patterns in (binary) matrices. Moreover, we shall assume that the matrix C has m rows and n columns, and denote |S_{C}^{(2)}| by a_{m,n}.

Remark 1. The operations of complementation (replacing i with k − i) and reflection about any one of the four axes of symmetry of the square lattice (the vertical, horizontal and diagonal lines through the origin) are all involutions on the set of numbered polyominoes which preserve occurrences, in the sense that if χ is one of the above operations, and P, Q are numbered polyominoes, then P occurs in Q if and only if χ(P) occurs in χ(Q). Clearly, the same is true if χ is any composition of these operations. Note that reflecting a matrix about the line y = −x and reducing the shape corresponds to taking the transpose of the matrix. As in classical permutation avoidance, these operations are often useful in reducing the enumeration of pattern-avoiding polyominoes to a smaller number of cases (patterns).

2 Right angled polyomino patterns

A polyomino is right angled if it contains precisely three tiles, two rows and two columns. There are four different right angled shapes: , , and

, each of which can be numbered in 8 different ways. The operations mentioned in Remark 1 give three equivalence classes here, that can be represented by , and . We now go on to see that in terms of avoidance, these three cases in fact reduce to two.

2.1 The pattern

We observe that since the pattern is its own transpose, a matrix avoids

if and only if its transpose does. So it is enough to consider matrices of size m × n, where m ≥ 2 and n ≥ m.

Proposition 2. We have a_{2,n} = 2^{n+2} − 4 for n ≥ 1; a_{3,3} = 16; a_{3,n} = 0 for n ≥ 4; and a_{m,n} = 0 for n ≥ m ≥ 4.

Proof. Let A be an m × n matrix n ≥ m, that avoids the pattern .

The case m = 2. If the first column of A is \binom{1}{0} or \binom{0}{1} then obviously this column does not affect the rest of the matrix, and thus we have 2a_{2,n−1} possibilities to choose A in this case.

If the first column of A is \binom{0}{0} (the case \binom{1}{1} can be dealt with in the same way), then from the second entry onwards the first row of A can consist only of 1s since otherwise we have an occurrence of the pattern with the first column of A as the first column of the occurrence. Now, all the entries in the second row, except possibly the last one, must be 0, since otherwise we have a literal occurrence of the numbered shape , which is an occurrence of the pattern , with the first row of the occurrence contained in the first row of the matrix. Thus, in this case we can choose the first row in 2 ways and then choose the leftmost bottom entry in 2 ways. Summarizing our considerations, we get the following recurrence relation:

a_{2,n} = 2a_{2,n−1} + 4,

with a_{2,1} = 4. This gives that a_{2,n} = 2^{n+2} − 4.

The case m = 3. The fact that a_{3,3} = 16 is easy to check. Suppose n ≥ 4. Assume that the first row has three occurrences of the same letter b ∈ {0, 1} in the positions i_{1}, i_{2} and i_{3}, where i_{1} < i_{2} < i_{3}. Then the i_{1}-st and i_{2}-nd columns cannot have additional b’s since this would obviously give an occurrence of in A with the first row of the occurrence contained in the first row of the matrix. That means that the i_{1}-st and i_{2}-nd columns are both the column ( \begin{matrix}b \\ 1 − b \\ 1 − b \end{matrix} ), which leads to an occurrence of . Thus, if n > 4, a_{3,n} = 0 since we necessarily have at least three occurrences of the same letter in the first row. Moreover, if n = 4, the only possible case is when the first row consists of exactly two 0’s and two 1’s.

Let us now show that in this case A must contain the pattern , and thus a_{3,4} = 0. Indeed, suppose 1’s occur in the positions i_{1} and i_{2}, i_{1} < i_{2}, and 0’s occur in the positions j_{1} and j_{2}, j_{1} < j_{2}. The i_{1}-st column must be ( \begin{matrix}1 \\ 0 \\ 0 \end{matrix} ) (in order to avoid a literal occurrence of the numbered shape with the first row contained in the first row of the matrix) while the j_{1}-st column must be ( \begin{matrix}0 \\ 1 \\ 1 \end{matrix} ) (in order to avoid a literal occurrence of the numbered shape

with the first row contained in the first row of the matrix). Moreover, the entry A_{2,i_{2}} is 1, since otherwise A_{3,i_{1}}A_{2,i_{1}}A_{2,i_{2}} forms the pattern . The entry A_{2,j_{2}} is 0, since otherwise A_{3,j_{1}}A_{2,j_{1}}A_{2,j_{2}} forms the pattern . Now, i_{2} must be less then j_{1}, since otherwise A_{3,j_{1}}A_{2,j_{1}}A_{2,i_{2}} forms the pattern . Thus, i_{1} < j_{2} and A_{3,i_{1}}A_{2,i_{1}}A_{2,j_{2}} forms the pattern , contradicting the fact that A avoids . So, a_{3,4} = 0.

The case m = 4. Follows from the case m = 3 and n ≥ 4.

2.2 The pattern

Proposition 3. We have

∑_{m,n≥0} a_{m,n}x^{m}y^{n} = ∑_{m≥0} \frac{\frac{x^{n}y}{1−(n+1)y}}{∏_{j=0}^{m} (x + \frac{(1−x)y}{1−jy})}.

Proof. Let A be an m × n matrix, that avoids the pattern .

The case m = 2. If the first column of A is \binom{0}{0}, \binom{1}{0}, or \binom{1}{1} then obviously this column does not affect to the rest of the matrix, and thus we have 3a_{2,n−1} possibilities to choose A in this case.

If the first column of A is \binom{0}{1} then the first row of A must consist of 0’s, since otherwise we have an occurrence of the pattern with the first column of A as the first column of the occurrence. But in this case, the entries A_{2,i}, for 2 ≤ i ≤ n, may be arbitrary, since they obviously can not be involved in an occurrence of . This gives 2^{n−1} possibilities to choose the matrix A. Thus, a_{2,n} = 3a_{2,n−1} + 2^{n−1}, and a_{2,0} = 1, since the empty matrix avoids . Hence, by induction on n it is easy to see that a_{2,n} = 2 · 3^{n} − 2^{n} for all n ≥ 0.

The case m > 2. Assume first that A_{1,1} = 0. If all the entries in the first row of A are 0’s, then the first row does not affect the rest of the matrix, and thus can be removed. So, in this case the number of such matrices is a_{m−1,n}. If the first row contains a 1, then the first column of A must consist of 0’s, since otherwise there would be an occurrence of in A involving the entry A_{1,1}. But in this case, the first column does not affect the rest of the matrix and can be removed. The number of such matrices is a_{m,n−1} − a_{m−1,n−1}, where we subtract the number of the m × (n − 1) matrices that have the first row consisting of 0’s (we do this since A contains a 1 in the first row).

Suppose now that A_{1,1} = 1, and that the entries A_{1,2}A_{1,3} … A_{1,n} give a word of the form \underbrace{11 … 1}_{i} \underbrace{00 … 0}_{n−i−1}, where 0 ≤ i ≤ n − 1. In this case, the first

row does not affect the rest of A and therefore can be deleted. There are n possibilities to choose the first row, and therefore n · a_{m−1,n} ways to choose the matrix A. The only remaining case to be considered is when the first row of A has the following structure:

1W_{1}01W_{2},

where the length of W_{1} is i, 0 ≤ i ≤ n − 3 (which implies that the length of W_{2} is n − i − 3), W_{1} has j 0’s, and W_{2} is a word of the form \underbrace{11 … 1}_{k} \underbrace{00 … 0}_{n−i−k−3},

where 0 ≤ k ≤ n−i−3. We observe that those columns to the left of W_{2} that have a 0 in the first position must consist entirely of 0’s, since otherwise we would have an occurrence of the pattern involving the entry A_{1,i+3} = 1. These columns can be removed since their entries can not be involved in an occurrence of the pattern . After removing these j +1 columns, we are left with an m×(n−j −1) matrix having the first row of the form \underbrace{11 … 1}_{i} \underbrace{00 … 0}_{n−i−1},

where 2 ≤ i ≤ n − 1. As was discussed before, this row can be removed. Summarizing our considerations, the number of possibilities to choose A with the first row of the form 1W_{1}01W_{2} described above is

∑_{i=0}^{n−3} ∑_{j=0}^{i} \binom{i}{j}(n − i − 2)a_{m−1,n−j−1},

because, once we fix i and j, we can choose the positions for the j zeros in \binom{i}{j} ways, and the entries A_{1,i+4}A_{1,i+5} … A_{1,n} in (n − i − 2) ways. Taking into account all the cases, we obtain the recursion:

\begin{matrix}a_{m,n} = (n + 1)a_{m−1,n} + a_{m,n−1} − a_{m−1,n−1} \\ + ∑_{i=0}^{n−3} ∑_{j=0}^{i} \binom{i}{j}(n − i − 2)a_{m−1,n−j−1}, \end{matrix}

for all m ≥ 3 and n ≥ 1, with a_{m,0} = a_{0,n} = 1 (since the empty matrix avoids any non-empty pattern), a_{m,1} = 2^{m} and a_{1,n} = 2^{n} (since one-dimensional matrices avoid our pattern), a_{m,2} = 2 · 3^{m} − 2^{m} and a_{2,n} = 2 · 3^{n} − 2^{n}. Rewriting the above in equivalent form, we obtain, for m ≥ 1 and n ≥ 3,

\begin{matrix}a_{m,n} = (n + 1)a_{m−1,n} + a_{m,n−1} − a_{m−1,n−1} \\ + ∑_{i=0}^{n−3} (∑_{j=i}^{n−3} \binom{k}{i}(n − 2 − i)) a_{m−1,n−1−i}, \end{matrix}

whence, using the identity ∑_{j=a}^{n−3} \binom{j}{a}(n − 2 − j) = \binom{n−1}{a+2}, we derive

a_{m,n} = (n + 1)a_{m−1,n} + a_{m,n−1} − a_{m−1,n−1} + ∑_{i=0}^{n−3} \binom{n − 1}{i + 2}a_{m−1,n−1−i},

or equivalently, for m ≥ 1 and n ≥ 2,

a_{m,n} = 2a_{m−1,n} + a_{m,n−1} − a_{m−1,n−1} + ∑_{i=1}^{n−1} \binom{n − 1}{i}a_{m−1,n+1−i}.

Let a(x, y) = ∑_{m,n≥0} a_{m,n}x^{m}y^{n}. We now translate this recursion into a functional equation in the generating function a(x, y), by dealing with the individual terms one by one. Using the facts that a_{m,0} = a_{0,n} = 1, a_{m,1} = 2^{m}, a_{1,n} = 2^{n}, a_{m,2} = 2 · 3^{m} − 2^{m}, and a_{2,n} = 2 · 3^{n} − 2^{n}, we obtain

1.

\begin{aligned}∑_{m≥1,n≥2} a_{m,n}x^{m}y^{n} & = ∑_{m≥0,n≥2} a_{m,n}x^{m}y^{n} − ∑_{n≥2} a_{0,n}y^{n} \\ & = a(x, y) − \frac{y}{1−2x} − \frac{1}{1−x} − \frac{y^{2}}{1−y}. \end{aligned}

\begin{aligned}∑_{m≥1,n≥2} a_{m−1,n}x^{m}y^{n} & = x ∑_{m≥0,n≥2} a_{m,n}x^{m}y^{n} \\ & = x (a(x, y) − \frac{y}{1−2x} − \frac{1}{1−x}) . \end{aligned}

3.

\begin{aligned}∑_{m≥1,n≥2} a_{m,n−1}x^{m}y^{n} & = y ( ∑_{m≥0,n≥1} a_{m,n}x^{m}y^{n} − ∑_{n≥1} a_{0,n}y^{n}) \\ & = y (a(x, y) − \frac{1}{1−x} − \frac{y}{1−y}) . \end{aligned}

4.

\begin{aligned}∑_{m≥1,n≥2} a_{m−1,n−1}x^{m}y^{n} & = xy ∑_{m≥0,n≥1} a_{m,n}x^{m}y^{n} \\ & = xy (a(x, y) − \frac{1}{1−x}) . \end{aligned}

5.

∑_{m≥1,n≥2} ∑_{i=1}^{n−1} \binom{n−1}{i}a_{m−1,n+1−i}x^{m}y^{n}

= xy ∑_{m≥0,n≥1} ∑_{i=1}^{n} \binom{n}{i}a_{m,n+2−i}x^{m}y^{n}

= xy ∑_{m≥0,n≥1} (∑_{i=0}^{n} \binom{n}{i}a_{m,n+2−i}x^{m}y^{n} − a_{m,n+2})

= x ∑_{n≥0,m≥2} a_{n,m} (\frac{y^{m−1}}{(1−y)^{m−1}} − y^{m−1}) x^{n}

= \frac{x(1−y)}{y} [a (x, \frac{y}{1−y}) − \frac{y}{(1−y)(1−2x)} − \frac{1}{1−x}] − \frac{x}{y} [a(x, y) − \frac{y}{1−2x} − \frac{1}{1−x}] .

Combining 1-5 and the recursion on a_{m,n} we conclude that

a(x, y) = \frac{y}{(1 − y)(x + (1 − x)y} + \frac{x}{x + (1 − x)y} a (x, \frac{y}{1 − y} ) .

The result follows by repeatedly applying this recursion and taking the limit.

2.3 The pattern

One can apply the same considerations made in Subsection 2. The only difference between these cases is that instead of 0’s below each 0 in the first row, we have 1’s. This gives a recursive bijection between the matrices avoiding the pattern and those avoiding the pattern . Thus we obtain the following analogous result.

Proposition 4. We have

∑_{m,n≥0} a_{m,n}x^{m}y^{n} = ∑_{m≥0} \frac{\frac{x^{n}y}{1−(n+1)y}}{∏_{j=0}^{m} (x + \frac{(1−x)y}{1−jy})}.

3 Square polyomino patterns

The square shape is the one with precisely four tiles, two rows and two columns. The operations in Remark 1 subdivide the sixteen square patterns into four equivalence classes, which can be represented by the patterns ,

, , and .

3.1 The pattern

We make the same observation made in Section 2, i.e. a numbered polyomino avoids the pattern if and only if its transpose avoids the transpose of , which is itself. So, it is enough to consider matrices of size m × n with m ≥ 2 and n ≥ m. Moreover, the pattern has the following properties that are easy to see:

1) A numbered polyomino avoids if and only if its complement does.

2) Permuting columns and rows of a numbered polyomino M produces a matrix M_{1} that avoids the pattern if and only if M does.

3) Permuting rows of a matrix M produces a matrix M_{1} that avoids the pattern if and only if M does.

Proposition 5. We have that a_{2,n} = (n^{2} +3n+4)2^{n−2} for n ≥ 0; a_{3,3} = 168; a_{3,4} = 408; a_{4,4} = 3240; a_{3,n} = a_{4,n} = 720 for n = 5, 6; a_{3,n} = a_{4,n} = 0 for n > 6; and a_{m,n} = 0 for n ≥ m ≥ 5.

Proof. Let A be an m × n matrix, that avoids the pattern .

The case m = 2. We consider only the case A_{1,1} = 0, since the case A_{1,1} = 1 gives the same number of matrices avoiding by property 1 above.

If A_{2,1} = 1 then the first column of A does not affect the rest of the matrix, and therefore we have a_{2,n−1} possibilities to choose A in this case. If A_{2,1} = 0 then no column of A other than the first can be \binom{0}{0} since this leads to an occurrence of in A. On the other hand, A obviously cannot contain two columns which are both copies of \binom{1}{1}. So, either A does not contain \binom{1}{1} or it contains precisely one such column. In the first case we have 2^{n−1} possiblities for A, since any column except the first one is either \binom{1}{0} or \binom{0}{1}. In the second case, we can choose the position in which we have \binom{1}{1} in (n − 1) ways, and then choose all other columns in 2^{n−2} ways. Thus we get the recurrence

a_{2,n} = 2 · (a_{2,n−1} + (n + 1)2^{n−2}),

which gives the desired result.

The case m = 3. To deal with this case we make use of the following four facts. Fact 1. There are no columns in A that are equal to each other. This is easy to see, since otherwise we have an occurrence of the pattern .

Fact 2. If both of the columns ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) and ( \begin{matrix}1 \\ 1 \\ 1 \end{matrix} ) appear in A, then A cannot have more than two columns. Indeed, using the fact that permuting the columns of A does not affect avoidance of the pattern , we can assume

that the first two columns of A are ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) and ( \begin{matrix}1 \\ 1 \\ 1 \end{matrix} ). Adding one more column

will introduce an occurrence of the pattern , since it will contain either two 1’s or two 0’s. Fact 3. If A contains either the column ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) or the column ( \begin{matrix}1 \\ 1 \\ 1 \end{matrix} ) then the other columns can only be chosen from a set consisting of three columns, without repetitions. In the first case these columns are ( \begin{matrix}0 \\ 1 \\ 1 \end{matrix} ), ( \begin{matrix}1 \\ 0 \\ 1 \end{matrix} ), and

( \begin{matrix}1 \\ 1 \\ 0 \end{matrix} ), whereas in the second case they are ( \begin{matrix}1 \\ 0 \\ 0 \end{matrix} ), ( \begin{matrix}0 \\ 1 \\ 0 \end{matrix} ), and ( \begin{matrix}0 \\ 0 \\ 1 \end{matrix} ). This is easy to see, since otherwise we obviously have an occurrence of the pattern

.

Fact 4. If A does not contain ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) or ( \begin{matrix}1 \\ 1 \\ 1 \end{matrix} ) then the columns of A can be chosen among all the other six binary columns of length 3 without repetitions. This follows from the fact that once such a column contains the same letter in two positions, the third entry is uniquely determined, and thus any two such columns will give an occurrence of if and only if they are equal.

As a corollary of Facts 1–4 we have the following:

a_{3,3} = 2 · 4! + \frac{6!}{3!} = 168; a_{3,4} = 2 · 4! + \frac{6!}{2!} = 408;

a_{3,5} = a_{3,6} = 6! = 720; a_{3,n} = 0 if n > 6,

where, for instance, to count a_{3,3} we first count the number of those matrices that have either ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) or ( \begin{matrix}1 \\ 1 \\ 1 \end{matrix} ) as a column (of which, according to Fact 3, there are precisely 2 · 4!), and then we add the number of matrices that do not contain ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) or ( \begin{matrix}1 \\ 1 \\ 1 \end{matrix} ) (of which, according to Fact 4, there are as many as there are permutations of three columns chosen from six columns).

The case m = 4. Suppose first that n ≥ 5. If a column of A has either at least three 0’s or at least three 1’s, then we can consider the three rows that form a matrix having the column ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) or ( \begin{matrix}1 \\ 1 \\ 1 \end{matrix} ). The length of such a matrix, according to Fact 3, does not exceed 4, and the columns of A in this case are those that have exactly two 0’s and two 1’s. It is easy to see that any combination of such columns gives no occurrences of the pattern

, and there are six such columns. Thus, a_{4,5} = a_{4,6} = 6! = 720.

Now let n = 4. If any column of A has exactly two 0’s and two 1’s, the number of ways to choose A in this case is \frac{6!}{2!} = 360. If some column has only 0’s or only 1’s, say only 0’s, then the number of columns does not exceed 2, since the other columns cannot have more than 1 zero, and two such columns must have an occurrence of the pattern . So, we need only consider the case when there is a column in A having three 0’s or three 1’s. Suppose there is a column with three 0’s. In this case we can assume, permuting rows or columns if necessary, that A_{1,1} = A_{2,1} = A_{3,1} = 0 and A_{4,1} = 1. If we consider the submatrix that is formed by the first three rows and the four columns, then according to the considerations of the case m = 3, this submatrix is a permutation of the columns ( \begin{matrix}0 \\ 1 \\ 1 \end{matrix} ), ( \begin{matrix}1 \\ 0 \\ 1 \end{matrix} ), and ( \begin{matrix}1 \\ 1 \\ 0 \end{matrix} ). Obviously, the entries A_{4,2}A_{4,3}A_{4,4} form a word that has at most one 1. Thus, there are 4 ways to choose this word, and then we can permute columns and rows in 4! · 4! ways to get different 4 × 4 matrices avoiding . So, in this case we have 4 · 24 · 24 = 2304 different matrices. Finally, we need to count the number of matrices that have a column with three 1’s and have no columns with three 0’s. We use the same considerations as in the case of three 0’s, but now we observe that the entries A_{4,2}A_{4,3}A_{4,4} can only form the word 111 (otherwise we have a column with three 0’s or an occurrence of the pattern ). Thus this case gives us 4! · 4! = 576 different matrices. So the total the number of 4 × 4 matrices avoiding the pattern is given by 360 + 2304 + 576 = 3240.

The case m ≥ 5. The first row of A has either at least three 0’s or at least three 1’s. In either case, if we consider the three rows of A that begin with the same letter, we have that, according to Fact 3, the length of these rows does not exceed 4, since otherwise they will contain the pattern . Thus, A must have less than or equal to four columns in order to avoid .

The fact that only a finite number of matrices avoid the pattern can be generalized to the case of an arbitrary rectangular pattern consisting of 0’s only. Let O_{ℓ,k} denote the rectangular pattern whose numbering is the constant 0, and having ℓ rows and k columns. In particular, O_{2,2} = . The following proposition holds.

Proposition 6. Let a_{m,n} denote the number of matrices that avoid the pattern O_{ℓ,k}. We have that a_{m,n} = 0 for m ≥ 2ℓ − 1 and n > 2(k − 1)\binom{2ℓ−1}{ℓ}.

Proof. Suppose m = 2ℓ − 1 and A is an m × n matrix that avoids O_{ℓ,k}. By the Dirichlet Principle, each column of A has either at least ℓ 1’s or at least ℓ 0’s. We encode each column of A by an ℓ-tuple (a_{1}, a_{2}, …, a_{ℓ}), where a_{i}, for 1 ≤ i ≤ ℓ, is the position in which the column under consideration has the same letter (0 or 1). Also, we assume that a_{1} < a_{2} < ⋯ < a_{ℓ}. In the case of more than ℓ equal letters, we choose any ℓ of them. Thus, for instance, the column (11011)^{T} (the superscript “T” denotes the operation of transposition) can be encoded by (1, 2, 4) as well as by (1, 3, 4) or by (2, 3, 4).

Suppose we have 2(k − 1) copies of all \binom{2ℓ−1}{ℓ} different ℓ-tuples, of which (k−1) copies correspond to the columns with at least ℓ 1’s, and the remaining (k−1) copies correspond to the columns with at least ℓ 0’s (since the columns are of length (2ℓ − 1) there are no problems with separating copies into those corresponding to 1’s and those corresponding to 0’s). We now collect all the columns corresponding to these ℓ-tuples (in any order) to build a (2ℓ−1)×2(k−1)\binom{2ℓ−1}{ℓ} matrix B. If we add any column to B and encode the columns of B, we will get k identical ℓ-tuples corresponding to occurrences of either at least ℓ 1’s or at least ℓ 0’s. But in this case we will get an occurrence of the pattern O_{ℓ,k}. So, for the matrix A, n ≤ 2(k − 1)\binom{2ℓ−1}{ℓ}. This bound cannot be improved since if we assume that each column among the 2(k − 1)\binom{2ℓ−1}{ℓ} columns has exactly ℓ entries equal to 1 or 0 then the matrix B avoids the pattern O_{m,n} (this is easy to see).

3.2 The patterns , , and

In this section we see how the transfer matrix method can be used to give a complete answer for finding the formula of the number of binary matrices of size m × n avoiding a pattern from the set S = { , , }, for any given m ≥ 1.

For fixed m ≥ 1 and p ∈ S, we denote by B^{m,∗} (B^{m,n}) the set of all binary matrices with m rows (m rows and n columns respectively), and define an equivalence relation ∼_{p} on B^{m,∗} by: A ∼_{p} B if for all vectors u ∈ B^{m,1} we have

A|u avoids p if and only if B|u avoids p

where the notation A|u stands for the matrix obtained by concatenating the

vector u to the matrix A. For example, if p is , m = 2, A = ( \begin{matrix}1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{matrix} )

and B = ( \begin{matrix}1 & 0 \\ 0 & 1 \\ 0 & 0 \end{matrix} ), then A ∼_{p} B, since the third column in A is never

contained in an occurrence of p. Let E_{p} be the set of equivalence classes of ∼_{p}. We denote the equivalence class of a binary matrix A by \overline{A}. For example, the equivalence classes of ∼_{p} for p = and m are

\overline{ϵ}, \overline{( \begin{matrix}0 \\ 0 \end{matrix} )}, and \overline{( \begin{matrix}0 & 0 \\ 0 & 1 \end{matrix} )}

where ϵ stands for the empty matrix.

Definition 7. Given a positive integer k and a pattern p we define a finite automaton^{2}, A_{p} = (E_{p}, δ, \overline{ϵ}, E_{p} \ \{\overline{p}\}), by the following:

• the set of states, E_{p}, consists of the equivalence-classes of ∼_{p};

• δ : E_{p} × B^{m,1} → E_{p} is the transition function defined by δ(\overline{A}, u) = \overline{A|u};

• \overline{ϵ} is the initial state;

• and all states but \overline{p} are final states.

2For a definition of a finite automaton, see [2] and references therein.

We want to enumerate the number of binary matrices of size m × n avoiding the pattern p. We shall identify A_{p} with the directed graph^{3} with vertex set E_{p} \ \{\overline{p}\} and with a (labelled) edge ⟶^{u} from \overline{A} to \overline{B} if A|u ∼_{p} B. Note that, whenever we have an edge from \overline{A} to \overline{B}, the outdegree of \overline{B}, that is, the number of binary vectors u ∈ B^{m,1} such that B|u ≁_{p} B but B|u still avoids p, is strictly less than the outdegree of \overline{A}. Hence, we may choose binary matrices {A^{(i)}}_{i=1}^{e} as representatives of the vertices (equivalence classes), indexed in such a way that if i < j there is no edge from \overline{A^{(j)}} to \overline{A^{(i)}}; in particular there are no directed cycles in the graph, and \overline{A^{(1)}} = \overline{ϵ}. The transition matrix, T_{p}, of A_{p} is the e × e -matrix,

[T_{p}]_{ij} = |\{u ∈ B^{m,1} : δ(A^{(i)}, u) = \overline{A^{(j)}}\}|.

Thus [T_{p}]_{ij} counts the number of edges from \overline{A^{i}} to \overline{A^{j}}, and with the above choice of indices T_{p} is upper triangular.

Example 1. Let p = and fix m = 3; then it is easy to see that a possible choice of representatives is

A^{(1)} = ϵ, A^{(2)} = ( \begin{matrix}1 \\ 0 \\ 0 \end{matrix} ), A^{(3)} = ( \begin{matrix}0 \\ 1 \\ 0 \end{matrix} ), A^{(4)} = ( \begin{matrix}0 \\ 0 \\ 1 \end{matrix} ),

A^{(5)} = ( \begin{matrix}0 & 1 \\ 1 & 0 \\ 0 & 0 \end{matrix} ) and A^{(6)} = ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ).

The transition matrix T_{p} is

(\begin{matrix}4 & 1 & 1 & 1 & 0 & 1 \\ 0 & 4 & 0 & 0 & 1 & 1 \\ 0 & 0 & 4 & 0 & 1 & 1 \\ 0 & 0 & 0 & 4 & 0 & 2 \\ 0 & 0 & 0 & 0 & 4 & 1 \\ 0 & 0 & 0 & 0 & 0 & 4 \end{matrix}) .

Given a matrix A let (A; i, j) be the matrix with row i and column j deleted. Using the transfer matrix method (see [1, Theorem 4.7.2]) together with the automaton A_{p} we obtain our main result in this section.

3Here we are allowing loops and multiple edges, and following the terminology of [3].

Theorem 8. Let p be a pattern of a matrix of size 2×2. Then the generating function for |B^{m,n}(p)| is

∑_{n≥0} |B^{m,n}(p)|x^{n} = \frac{∑_{j=1}^{e} (−1)^{j+1} det(I − xT, j, 1)}{∏_{i=1}^{e}(1 − λ_{i}x)} = \frac{det B(x)}{∏_{i=1}^{e}(1 − λ_{i}x)},

where λ_{i} is the number of loops at state A^{(i)}, and B(x) is the matrix obtained by replacing the first column in I − xT with a column of all ones.

Theorem 8 provides a finite algorithm for finding the generating function for the sequence {B^{m,n}(p)}_{n≥0} for any given m ≥ 0 and a pattern p which is matrix of size 2 × 2. The algorithm has been implemented in C and Maple.

Corollary 9. For all n ≥ 0, (i) |B^{2,n}( )| = (3 + n)3^{n−3},

(ii) |B^{3,n}( )| = \frac{1}{3}(2 + n)(96 + 31n + n^{2})4^{n−3},

(iii) |B^{4,n}( )| = \frac{1}{36}(2812500 + 3963450n + 1862971n^{2} + 339300n^{3} + 21265n^{4} + 510n^{5} + 4n^{6})5^{n−7},

(iv) B^{5,n}( )| = \frac{1}{105}(1371372871680+2829503247984n+2174816371140n^{2}+ 785515085820n^{3}+139879643143n^{4}+12307090320n^{5}+579047595n^{6}+15070860n^{7}+ 218757n^{8} + 1656n^{9} + 5n^{10})6^{n−13}.

Corollary 10. For all n ≥ 0, (i) |B^{2,n}( )| = (3 + n)3^{n−3},

(ii) |B^{3,n}( )| = \frac{1}{3}(2 + n)(96 + 31n + n^{2})4^{n−3},

(iii) |B^{4,n}( )| = \frac{1}{36}(2812500 + 3963450n + 1862971n^{2} + 339300n^{3} + 21265n^{4} + 510n^{5} + 4n^{6})5^{n−7},

(iv) |B^{5,n}( )| = \frac{1}{350}(4571242905600+9431397663120n+7249916118636n^{2}+ 2618093085240n^{3}+466294991825n^{4}+41039857215n^{5}+1926425298n^{6}+50381010n^{7}+ 729825n^{8} + 5415n^{9} + 16n^{10})6^{n−13}.

Corollary 11. For all n ≥ 0, (i) |B^{2,n}( )| = (3 + n)3^{n−3}, (ii) |B^{3,n}( )| = (16 + 13n + 3n^{2})4^{n−2},

(iii) |B^{4,n}( )| = (25 + 34n + 18n^{2} + 3n^{3})5^{n−2},

(iv) |B^{5,n}( )| = (216 + 418n + 361n^{2} + 140n^{3} + 17n^{4})6^{n−3}.

Note that no two patterns in S give the same formulas, although the distinction between the patterns and does not become apparent before m = 5. We also remark that our approach can be generalized to matrices on k letters and simultaneously avoiding different configurations of polyomino patterns. For example, the following result is true.

Corollary 12. We have that:

(i) the number of matrices of size 3 × n on 3 letters avoiding the pattern is given by

\begin{matrix}\frac{1}{2}(1582178 − 269829n + 6241n^{2})13^{n−2} \\ −(673920 − 61130n − 4427n^{2} − 106n^{3} − n^{4})12^{n−2}; \end{matrix}

(ii) the number of binary matrices of size 2 × n simultaneously avoiding the patterns and is given by

2 · 3^{n} − 2^{n}.

References

[1] R. Stanley, Enumerative Combinatorics, Volume 1, Cambridge University Press, Cambridge, 1997.

[2] A. V. Aho, R. Sethi, J.D. Ullman, Compilers: principles, techniques and tools, Addison-Wesley, Reading, Mass., 1986.

[3] R. Diestel, Graph Theory, Springer-Verlag, New York, 1997.

[4] I. Jensen, A.J. Guttmann, Statistics of lattice animals (polyominoes) and polygons. J. Phys. A 33 (2000), no. 29, L257–L263.

[5] M.-P. Delest, G. Viennot, Algebraic languages and polyominoes enumeration. Theoret. Comput. Sci. 34 (1984), no. 1-2, 169–206.

[6] D. Hickerson, Counting horizontally convex polyominoes. J. Integer Seq. 2 (1999), Article 99.1.8, 1 HTML document (electronic).