How many simply connected subsets of an n-by-m grid? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T13:15:13Z http://mathoverflow.net/feeds/question/44162 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/44162/how-many-simply-connected-subsets-of-an-n-by-m-grid How many simply connected subsets of an n-by-m grid? Steve Flammia 2010-10-29T17:59:50Z 2010-11-05T00:29:34Z <p>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. </p> <hr> <p>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: </p> <blockquote> <p>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? </p> </blockquote> <p>Because the tiles are labeled, rotation or translation to get the same polyomino isn't allowed. I'm trying to count <em>all</em> 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.</p> http://mathoverflow.net/questions/44162/how-many-simply-connected-subsets-of-an-n-by-m-grid/44186#44186 Answer by Pietro Majer for How many simply connected subsets of an n-by-m grid? Pietro Majer 2010-10-29T22:17:01Z 2010-10-30T17:02:22Z <p>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 <a href="http://en.wikipedia.org/wiki/Polymino" rel="nofollow">polyominos</a>, thus in particular "solid agglomerates" of squares, and not e.g. two squares only joined by a vertex. </p> <p>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 <em>loop</em> I mean, a <em>closed path</em> in $\Gamma$ up to the initial point and up to orientation (that is, a loop is the image of a closed path). </p> <p>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.$$</p> <p>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). </p> <p>So, I 'm not sure if this leads somewhere. I'd be glad if somebody could show how to go on along this path.</p> http://mathoverflow.net/questions/44162/how-many-simply-connected-subsets-of-an-n-by-m-grid/44194#44194 Answer by sleepless in beantown for How many simply connected subsets of an n-by-m grid? sleepless in beantown 2010-10-30T00:04:26Z 2010-11-05T00:29:34Z <p></p> <p><strong>edit 3 : The original answer given apllies again</strong></p> <p>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.</p> <p>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.</p> <p><em>[edit 2] : old problem with this question as was previously posed</em></p> <p>It's possible to use the same vertex-set to define multiple polyominos, if rotation is not allowed, because a vertex-set alone is <em>not sufficient</em> to specify a polyomino shape and which edges need to be considered. </p> <blockquote> <p>Thus the question as posed, requesting vertex sets, is not rigorously defined enough to admit a solution.</p> </blockquote> <p>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:</p> <pre><code>1---2 3---4 1---2---3---4 | | | | | | 5 6---7 8 5 6---7 8 | | | | | | 9--10--11--12 9--10 11--12 </code></pre> <p>Thus, the <em>vertex set</em> alone is <strong>not sufficient</strong> 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).</p> <p>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.</p> <pre><code> 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 </code></pre> <h2>old answer is still below</h2> <p>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.</p> <p>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?</p> <p>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:</p> <ul> <li><p>call the total set of vertices $S$</p></li> <li><p>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}$.</p></li> <li><p>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$</p></li> <li><p>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$</p></li> </ul> <p>$S_a =${$v_1, v_2, ... , v_k$}</p> <p>$\forall v_j \in S_a, \textrm{distance}(v_j, S_a - v_j)=1$</p> <p>where $S_a - v_j$ represents the set generated by starting with $S_a$ and removing element $v_j$</p> <hr> <p>If instead of that approach, you are really talking about polyominos or the faces of the $m \times n$ lattice:</p> <p>You can generate the <em>dual</em> of this graph as the $(m-1)\times(n-1)$ lattice and count the number of single component subgraphs in that.</p> <p>In regard to JBL's comment to the question, I think you're right that Sequence A140517 at <a href="http://www.research.att.com/~njas/sequences/A140517" rel="nofollow">http://www.research.att.com/~njas/sequences/A140517</a> 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.</p> <p>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.</p>