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.
