4
$\begingroup$

I have a two dimensional n x m grid graph. And I want to find in how many ways this grid can be covered with simple cycles (it can be a one cycle or it can be many cycles) in such a way that every vertex is covered by only one cycle. Cycles of length 1 (that cover only one vertex) are not considered.

For example all of the 1xn grids would have $0$ cycles and for a 2x4 grid you can cover it with cycles in $2$ different ways:

and


Similar question was asked in a competition a couple of weeks ago and I only was able to come up with the following thoughts:

  • the answer for n x m = m x n, so I can consider only grids where $n \leq m$
  • for all 3xn grids the answer is $0$. Thanks to Calvin's comment now I see that this is not the case. Now I can find at least 3 ways to cover 3x4 grid with cycles
  • for all 2xn grids the answer is $fibonacci(n)$

But I am still unable to find the solution for a general case.

P.S. cycles can be non-convex, nested cycles allowed.

enter image description here

$\endgroup$
  • $\begingroup$ Right. I believe the answer is 3. For odd n, there are no solutions, but for even n there's always the "split into 3 by 2 cells". $\endgroup$ – Calvin Lin Jul 19 '15 at 21:31
  • 1
    $\begingroup$ For $2n\times 3$ there are $3^{n-1}$ different ways to cover it with cycles. $\endgroup$ – san Jul 27 '15 at 5:07
  • $\begingroup$ @san excellent finding. I am even more curious as of what is the formula for $C(n,m)$. By the way, feel free to post your comments as an answer for just these two cases (hopefully with explanation). This is not the question which will attract hundreds of views even with the bounty, so I highly doubt that some would answer it. $\endgroup$ – Salvador Dali Jul 27 '15 at 18:50
  • 1
    $\begingroup$ Thank you. I'll try 5xn and then I post the answer with details. $\endgroup$ – san Jul 28 '15 at 0:51
3
+50
$\begingroup$

There is no general formula for an $m\times n$ grid, but there is a recursive approach that allows to compute the number $C(m,n)$ of different ways to cover the grid with simple cycles for any $m,n$.

First note that once you have covered the grid, it suffices to know the horizontal lines, in order to determine all the cycles. So you can assign to each covering an $(n-1)$ tuples of subsets of $\{1,\dots,m\}$. Each subset indicates which horizontal lines
are part of the cycles, numbering the possible horizontal lines from 1 to $m$, the lowest one corresponding to 1.

I'll try to learn how to include graphics in my answers, for the moment I'll use the graphics provided by the OP. For the two different covering of a 2x4 grid, we have the 3-tuples $(\{1,2\},\emptyset,\{1,2\})$ and $(\{1,2\},\{1,2\},\{1,2\})$. To the covering of the 5x6 grid given above, the corresponding 5-tuple is $(\{1,5\},\{1,2,4,5\},\{1,2,3,5\},\{1,2,4,5\}, \{1,5\})$, whereas, if we rotate the grid by 90 degree, we obtain a covering of a 6x5 grid with the corresponding 4-tuple $(\{1,6\},\{1,2,3,4,5,6\},\{1,2,5,6\},\{1,6\})$.

Note that there must be an even number of horizontal lines, since they are part of simple cycles.

For a valid choice of horizontal lines $(X_1,X_2,\dots,X_{n-1})$ in an $m\times n$ grid, with $X_i\subset\{1,\dots,m\}$, there is exactly one form to add vertical lines in order to obtain simple cycles covering the grid: If a horizontel line $j\in X_k\cap X_{k+1}$, then there can be no vertical lines from $j-1$ to $j$ nor from $j$ to $j+1$. If you name the remaining endpoints increasingly with $c_1,\dots,c_k$, then you must connect $c_1$ with $c_2$, $c_3$ with $c_4$ and in general $c_{2i-1}$ with $c_{2i}$, with vertical lines, that do not intersect the connected horizontal lines. The connected horizontal lines and the vertical lines cover all points $1,\dots,m$.

In particular, if we apply this algorithm to a pair $S_0,S_1\subset \{1,\dots,m\}$, then we can obtain a valid two column grid or it may happen that it is not possible. For example, if $m=4$, then $\{1,4\},\{2,3\}$ is a valid match, but $\{1,2,3,4\},\{2,3\}$ is not, since you cannot connect $c_1=1$ with $c_2=4$ without intersecting the horizontal lines at 2 and 3. Similarly $\{2,3\},\{2,3\}$ is not a valid match, since it doesn't cover the point 1.

This gives us the necessary conditions on an $(n-1)$-tuple to be a valid choice:

DEFINITION:

An $(m,n)$-covering is an $(n-1)$-tuple $(X_1,\dots,X_{n-1})$ of subsets $X_i\subset \{1,\dots,m\}$, such that

  • Each $X_i$ has an even number of elements.

  • Set $X_0:=\emptyset$ and $X_n:=\emptyset$. Then $X_k,X_{k+1}$ must be a valid match for $k=0,\dots,n-1$.

This definition allows now to count the different ways to cover an $m\times n$ grid with simples cycles: It is the number of different $(m,n)$-coverings.

We now index the different valid choices of horizontal lines in a column. For the time being there are $2^{m-1}$ choices corresponding to the number of even subsets of $\{1,\dots,m\}$, we will see later that we can eliminate some of them. For example, if $m=2$ we have $S_0^{(2)}:=\emptyset$ and $S_1^{(2)}:= \{1,2\}$. Valid matches are $(S_0,S_1)$, $(S_1,S_0)$ and $(S_1,S_1)$, i.e., all but $(S_0,S_0)$ (We drop the superscript if $m$ is clear).

In the case of $m=3$, we have $S_0=\emptyset, S_1=\{1,2\},S_2=\{2,3\}$ and $S_3=\{1,3\}$. The valid matches are $(S_0,S_3)$, $(S_1,S_3)$, $(S_2,S_3)$ and their symmetric pairs. We can codify the valid matches in a matrix (called adjacency matrix), $$ A=\pmatrix{ 0&0&0&1\\ 0&0&0&1\\ 0&0&0&1\\ 1&1&1&0}. $$ Here $A_{i,j}=1$, if $(S_i,S_j)$ is a valid match, and 0 if it's not valid.

For $m=4$ we have $S_0=\emptyset, S_1=\{1,2\},S_2=\{2,3\}$, $S_3=\{3,4\}$, $S_4=\{1,4\}$ and $S_5=\{1,2,3,4\}$. The valid matches are given by the matrix $$ A=\pmatrix{ 0&0&0&0&1&1\\ 0&0&0&1&1&1\\ 0&0&0&0&1&0\\ 0&1&0&0&1&1\\ 1&1&1&1&0&1\\ 1&1&0&1&1&1}. $$

Note that the sets $\{1,3\}$ and $\{2,4\}$ can be matched only one with the other, and so they can be never part of a valid $(n-1)$-tuple, and can be dismissed.

Once you have the adjacency matrix, you can use it to compute $C(m,n)$: $$ C(m,n)=(A^n)(e_0))_0=(A^{n})_{0,0}, $$ i.e., you apply $n$ times the matrix $A$ to the column vector $e_0$ (corresponding to the empty set at $X_0$) and compute the $0$'th entry (corresponding to the emptyset at $X_{n}$).

In the case $m=2$ it is known that the matrix $$A=\pmatrix{0&1\\ 1&1}$$ corresponds to the Fibonacci sequence. In our case we start with $a_1=0$ and $a_2=1$, and obtain $C(2,n)=a_n$.

In the case $m=3$ a straightforward computation shows that $C(3,2n+1)=0$ and, since $$ A^{2n-1}=3^{n-1}\pmatrix{ 0&0&0&1\\ 0&0&0&1\\ 0&0&0&1\\ 1&1&1&0}, $$ we have $C(3,2n)=3^{n-1}$.

${\bf{EDIT}}$: A covering of an $m\times n$ grid is called a 2-factor of $P_m\times P_n$ or also a spanning 2-regular subgraph (it covers all vertices: spanning, every vertex has two edges: 2-regular, the edges are contained in the grid: subgraph). In table 3 of http://www.emis.de/journals/PIMB/070/n070p023.pdf the number of 2-factors are given for $2\le m\le 7$ and $2\le n\le 10$. In the same article the method of the adjacency matrix is explained, although the method to obtain these matrices seems more complicated than the method explained above. The author also gives the generating functions for the recurrence relations for $f_m(n):=C(m,n)$ for $m=2,\dots, 7$.

In https://oeis.org/A003693 the recursion formula for $a(n)=C(4,n)$ is given: $$ a(n) = 2a(n-1) + 7a(n-2) - 2a(n-3) - 3a(n-4) + a(n-5) $$ for $n>5$, and the first five terms are $0,2,3,18,54$.

In https://oeis.org/A003776 the recursion formula for $b(n)=C(5,2n)$ is given: $$ b(n) = 24b(n-1) - 57b(n-2) + 26b(n-3), $$ for $n>3$, and $b(1)=C(5,2)=3$, $b(2)=C(5,4)=54$ and $b(3)=C(5,6)=1140$. Moreover, the author of http://www.emis.de/journals/PIMB/070/n070p023.pdf says that it is easy to prove that $C(n,m)>0$ iff $m\cdot n$ is even, hence $C(5,2n+1)=0$, for all $n$.

In https://oeis.org/A222202 the values of $C(2n,2n)$ are given, and in https://oeis.org/A222203 the values of $C(n,n+1)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.