[Math] Count Number rectangles of 1s In a grid

combinatorics

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 1×2 or 2×1 the answer is 0.

for a 2×2 grid we have only 1 such case

1 1
1 1

making count=1.

Plz help find the count.

Best Answer

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.

Related Question