Counting the number of minimal covers of a binary matrix Given a binary $n$-times-$n$ matrix $A$, we'd like to cover the regions comprised of $1$'s with non-intersecting rectangles. A collection of disjoint rectangles that covers all $1$'s (and only $1$'s, i.e., it mustn't cover any $0$'s) is called a cover. (Notice that a problem instance may have many different covers.)

A cover is called a minimum cover if it uses the smallest number of rectnagles possible.

The counting problem I'm interested in is: given an $n$-times-$n$ binary matrix $A$, count the number of minimum covers of $A$.

What can you say about this problem? (This post was inspired by this SO question.)
It's easy to show that some inputs can produce an exponential number of minimum covers.  Consider the following 3x3 matrix:

110
100
000


This can be minimally covered in exactly 2 ways: either using a single vertical 2x1 rectangle and a single 1x1 rectangle, or a single horizontal 1x2 rectangle and a single 1x1 rectangle.

Thus placing $k$ non-overlapping copies of this gadget in a grid will produce an instance with $2^k$ distinct minimal covers.  You could, for example, tile an $n$ by $n$ grid with $n^2/9$ of them to produce an instance with $2^{n^2/9}$ minimal covers.

(It's possible that a better gadget exists -- that is, smaller gadgets that would increase the coefficient in the exponent.  More interestingly it's possible that instances with asymptotically more minimal covers exist.)