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.
 A: 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.
