Given an n-by-m square grid graph, how many ways are there to choose a subset of the vertices which is simply connected? Here, a subset of vertices is simply connected if the vertices, together with any edges or interior faces connecting them amongst themselves, form a contractible subregion of the grid. More formally, we can naturally embed the grid graph into the plane. Then I want to count subsets of vertices such that the union of the dual 2-cells forms a simply connected region in the plane.
Let me try to be a little bit clearer this time. Let's work directly with the dual, since that is easier to visualize. Hence, my question is:
Consider a grid of square tiles of dimensions n-by-m, with each of the nm tiles distinctly labeled. How many distinct (labeled) simply connected subsets of tiles are there as a function of n and m?
Because the tiles are labeled, rotation or translation to get the same polyomino isn't allowed. I'm trying to count all subsets. Commenter JBL points out the sequence for m=n at Sloane's, which also links to a lot of work by Artem M. Karavaev on this problem.
Best Answer
$$ $$
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] : old problem with this question as was previously 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:
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).
Here's my example of a 16-vertex set for $m=4, n=4$ which generates two different polyominos which remain distinct even under rotation.
old answer is still below
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://oeis.org/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.