# Count Number rectangles of 1s In a grid

Suppose we have a binary grid(filled with 0s and 1s) with x rows and y columns. what is number of ways the grid can be filled such at it has AT LEAST one rectangular block of 1s. Given the condition that A rectangle is any set of 1s that form a boxed area with width and length > 1. A square is also a rectangle but 1,1 is not.

for 1x2 or 2x1 the answer is 0.

for a 2x2 grid we have only 1 such case

1 1
1 1

making count=1.

Plz help find the count.

• You may as well replace "at least one rectangular block" by "at least one 2x2 block" (since any grid containing the former contains the latter). For squares, the OEIS has values for the number of grids WITHOUT a 2x2 block of 1's at oeis.org/A139810 , but there's no further information given. – Kevin P. Costello Nov 6 '12 at 19:13
• For a grid of fixed height and arbitrary width, an explicit formula or generating function can be obtained for grids that don't contain a $2\!\times\!2$ block of $1$s by using the "transfer matrix" method. As is often the case with this type of problem, it is unlikely that a closed formula or generating function can be found for grids of arbitrary width and height. – David Bevan Nov 7 '12 at 10:00
• @DavidBevan: Could give a formula insight on lets say 3 row matrix with say c columns – Fluvid Nov 7 '12 at 10:10

We will count $n\!\times\!3$ grids containing no $2\!\times\!2$ block of $1$s ("three-row square-free grids"):

If we encode the columns by integers using the entries as the digits of a binary number, then for three rows, we have three classes of columns: $A=\{0,1,2,4,5\}$, $B=\{3,6\}$ and $C=\{7\}$, with transfer matrix $M=\Big(\begin{smallmatrix}5&2&1\\5&1&0\\5&0&0\end{smallmatrix}\Big)$.

The number of three-row square-free grids is thus the sum of the entries in the vector $$(5,2,1)\,M^{n-1}.$$ The closed form is complex, involving roots of cubic polynomials.

The first few terms are $8, 57, 417, 3032, 22077, 160697, 1169792, 8515337, 61986457, 451223152$. This is A181246 in OEIS.

Alternatively, if we let $a(z)$, $b(z)$ and $c(z)$ be the (ordinary) generating functions for $n\!\times\!3$ square-free grids where the final column is in classes $A$, $B$ and $C$ respectively, and we let $g_3(z)$ be the OGF for all three-row square-free grids, then solving the equations $$\begin{array}{rcl}a(z) &=& 5 z + z\:\! (5 a(z) + 5 b(z) + 5 c(z))\\ b(z) &=& 2 z + z\:\! (2 a(z) + b(z))\\c(z) &=& z + z\:\! a(z)\\g_3(z)&=&a(z)+b(z)+c(z)\end{array}$$ gives $$g_3(z)\;=\;\frac{z\:\! (8 + 9 z - 5 z^2)}{1 - 6 z - 10 z^2 + 5 z^3}.$$

For four-row grids, five classes are required, with transfer matrix $\left( \begin{smallmatrix} 8 & 4 & 1 & 2 & 1 \\ 8 & 2 & 1 & 1 & 0 \\ 8 & 4 & 0 & 0 & 0 \\ 8 & 2 & 0 & 0 & 0 \\ 8 & 0 & 0 & 0 & 0 \end{smallmatrix} \right)$, giving generating function $\frac{8 z (2+7 z+z^2-8 z^3)}{1-10 z-54 z^2-16 z^3+64 z^4}$.

There are many numerical results in OEIS: three rows, four rows, five rows, six rows, seven rows, eight rows, and nine rows.

• Bean: Could you point me to a link or material where I could find how you got the classes A, B ,C and M. – Fluvid Nov 7 '12 at 17:07
• also what if we need to count no 2x2 block of four 1s or 0s – Fluvid Nov 7 '12 at 17:20
• The classes correspond to columns with the same transition behaviour -- i.e. given classes $X$ and $Y$, every column in class $X$ must be able to be followed by the same number of elements (but not necessarily the same elements) of class $Y$. Columns in class $A$ have no adjacent $1$s; columns in class $B$ have two adjacent $1$s; the column in class $C$ has three adjacent $1$s. – David Bevan Nov 7 '12 at 18:42
• Bean: can we extend the logic to say there should be no 2x2 sub matrix of 0 and there will be no 2x2 submatrix for 1s – Fluvid Nov 7 '12 at 18:55
• The same approach works avoiding both $2\!\times\!2$ blocks of $1$s and $2\!\times\!2$ blocks of $0$s. Because of the symmetry between $1$ and $0$, for three-row grids, three classes are still sufficient: $\{0,7\}$, $\{1,3,4,6\}$ and $\{2,5\}$. – David Bevan Nov 7 '12 at 19:21