How many simply connected subsets of an n-by-m grid? - MathOverflow

How many simply connected subsets of an n-by-m grid?

2010-10-29T17:59:50Z

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.

Answer by Pietro Majer for How many simply connected subsets of an n-by-m grid?

2010-10-29T22:17:01Z

This seems quite difficult, but maybe something can be done. Here's some hints, I hope it's useful. In the following I assume that you want simply connected polyominos, thus in particular "solid agglomerates" of squares, and not e.g. two squares only joined by a vertex.

A simply connected polyomino in the rectangle $[0,n]\times[0,m],$ with vertices of integer coordinates, is precisely determined by its boundary, which may be seen as a closed simple loop in your $n$-by-$m$ square grid graph $\Gamma_{n,m}=(V,E).$ So what you want is precisely the number $N$ of closed simple loops in the graph $\Gamma$. Here by loop I mean, a closed path in $\Gamma$ up to the initial point and up to orientation (that is, a loop is the image of a closed path).

Thus we may write $N=\sum_{k\ge 1} \frac{C(k)}{2k},$ denoting by $C(k)$ the number of simple closed loops of length $k$ (so a simple closed loop of length $k$ is precisely a $k$ ple of distinct vertices $v_1,\dots,v_{k-1}, v_k=v_0$ such that $v_i$ and $v_{i+1}$ are adjacent for $i=1\dots k$). If we denote $c=\sum_k C(k) t ^k $ the GF of the sequence $C(k)$ (a polynomial indeed), we can write $$N:=\int_0^1\frac{c(t)}{2t}dt. $$

Let's then denote $P(u,v,k)$ the number of oriented paths of length $k$ starting at the vertex $v$ and ending at the vertex $u.$ This should be the simplest quantity to compute, for no injectivity is assumed on the paths (it's the $(u,v)$ coefficient in the $k$-power of the adjacency matrix of $\Gamma$ also). Then, I think that one could write $C(k)$ in terms of the $P(u,v,k)$ (via the GF or using the inclusion-exclusion formula. I tried before, with a wrong computation).

So, I 'm not sure if this leads somewhere. I'd be glad if somebody could show how to go on along this path.

Answer by sleepless in beantown for How many simply connected subsets of an n-by-m grid?

2010-10-30T00:04:26Z

$$ $$

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.

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).

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.

 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

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://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.