5
$\begingroup$

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.

  • 0
    @DavidBevan: Could give a formula insight on lets say 3 row matrix with say c columns2012-11-07

1 Answers 1

2

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.

  • 0
    [https://oeis.org/A133129](https://oeis.org/A133129) contains the numerical results for three rows avoiding $1$s and $0$s.2012-11-07