edit 3 : The original answer given apllies again

Now that the question is clarified and specified labeled square tiles (although now changing what $n$ and $m$ denote from the number of vertices along each dimension to now denoting the number of tiles' edges along each dimension) arranged in a $m \times n$ rectangular pattern, and asks about the number of simply connected subsets of tiles.

The number of simply-connected subset of tiles for an $m \times n$ rectangular array of labeled square tiles is equal to the number of different labeled graphs induced by rooted trees of size greater than or equal to $0$ nodes for the 2-dimensional lattice graph of size $m \times n$. The numbers given below, in the old version of the answers, assumes that $m$ and $n$ represented the number of vertices and $m-1$ and $n-1$ represented the number of faces or tiles in the dual-graph of the $m \times n$ lattice graph originally specified.

[edit 2] : new old problem with this question as currently was previously posed

5 extra example with 16 vertices

[edit 2] : new problem with this question as currently posed

It's possible to use the same vertex-set to define multiple polyominos, if rotation is not allowed, because a vertex-set alone is not sufficient to specify a polyomino shape and which edges need to be considered.

Thus the question as posed, requesting vertex sets, is not rigorously defined enough to admit a solution.

For $m=4, n=3$, the vertex set {$1,2, \cdots, 12$} consisting of all $12$ of the vertices can define two polyominos which are distinct if rotation is not allowed:

1---2   3---4       1---2---3---4
|   |   |   |       |           |
5   6---7   8       5   6---7   8
|           |       |   |   |   |
9--10--11--12       9--10  11--12


Thus, the vertex set alone is not sufficient to distinguish different valid polyominos. Vertices and edges must be specified; or alternatively for the dual the faces must be specified (as described in the older part of this answer, below).Thus the question as posed, requesting vertex sets, is not rigorously defined enough to admit

Here's my example of a solution16-vertex set for $m=4, n=4$ which generates two different polyominos which remain distinct even under rotation.

 1---2   3---4       1---2---3---4
|   |   |   |       |           |
5   6---7   8       5   6---7   8
|           |       |   |   |   |
9  10--11  12       9  10  11  12
|   |   |   |       |   |   |   |
13--14  15--16      13--14  15--16


If by your question you mean how many different subgraphs of an $m \times n$ lattice graph consist of a single connected component, rather than multiple components, then the answer is going to be different from Pietro Majer's approach.

In that case, for $m=n=2$, let's label each vertex in the lattice graph as $v_{x,y}$ with $1 \le x \le m$ and $1 \le y \le n$. Would you consider the selections $S_1=${$v_{1,1}, v_{1,2}, v_{2,1}$} and $S_2=${$v_{2,2}, v_{1,2}, v_{2,1}$} to be different selections of vertices or the same, because the single face adjoining these $2$ of the $4$ ways to select $3$ of the $4$ vertices in this case is considered part of the selection. If so, then would selecting a single edge on a face be considered as selecting the face of the polyomino?

If not, then there's another approach to the solution. Given an $m \times n$ lattice graph, with vertices labeled by their $x,y$ coordinates:

• call the total set of vertices $S$

• a subset $S_i \in S$ consists of $0$ to $m\cdot n$ vertices, and each subset can (for labeling's sake) be labeled with an integer $0 \le i \le 2^{mn}$.

• define the distance of one subset $S_a$ to another subset $S_b$ to be the minimal Manhattan distance from the elements of subset $S_a$ and subset $S_b$

• define a subset $S_a \in S$ as meeting your condition if the minimal distance of each vertex in that subset from the other elements of that subset is $1$

$S_a =${$v_1, v_2, ... , v_k$}

$\forall v_j \in S_a, \textrm{distance}(v_j, S_a - v_j)=1$

where $S_a - v_j$ represents the set generated by starting with $S_a$ and removing element $v_j$

If instead of that approach, you are really talking about polyominos or the faces of the $m \times n$ lattice:

You can generate the dual of this graph as the $(m-1)\times(n-1)$ lattice and count the number of single component subgraphs in that.

In regard to JBL's comment to the question, I think you're right that Sequence A140517 at http://www.research.att.com/~njas/sequences/A140517 is the right sequence for an $(n-1) \times (n-1)$ grid. I don't think the question's original poster has clarified the question well enough since the question still asks for "vertex subsets", rather than saying "faces" on the 2-d lattice. I have a different approach for a different answer below, where you can take the dual of the $m \times n$ lattice and get an $(m-1) \times (n-1)$ lattice with each vertex in this graph representing a face in the original lattice graph. Then, the count of the single component subgraphs of this dual is the answer.

The original poster needs to clarify the question and give some example answers to $m=2, n=2$. Does the solution for $m=2, n=2$ count only the single face generated by all $4$ vertices as the only solution, do the different sets of vertices taken three at a time count as separate solutions? Would taking two vertices that are distance $1$ apart count as a solution at all? The question really needs to be clarified.

4 Posted another object to this question's rigorousness: Vertex set alone is still ambiguous

[edit 2] : new problem with this question as currently posed

It's possible to use the same vertex-set to define multiple polyominos, if rotation is not allowed, because a vertex-set alone is not sufficient to specify a polyomino shape and which edges need to be considered.

For $m=4, n=3$, the vertex set {$1,2, \cdots, 12$} consisting of all $12$ of the vertices can define two polyominos which are distinct if rotation is not allowed:

1---2   3---4       1---2---3---4|   |   |   |       |           |5   6---7   8       5   6---7   8|           |       |   |   |   |9--10--11--12       9--10  11--12Thus, the vertex set alone is not sufficient to distinguish different valid polyominos.  Vertices and edges must be specified; or alternatively for the dual the faces must be specified (as described in the older part of this answer, below).  Thus the question as posed, requesting vertex sets, is not rigorously defined enough to admit a solution.old answer is still below

 
 
 
3 correct LaTeX errors, removed redundant text
2 clarified that the original question is not clear at all
1