How many edge-disjoint paths go from upper left to lower right in a $4 \times N$ rectangular gridwork of streets?

Question

Background/Motivation

My interest in this problem traces back to an 11 year old girl who really took to one-way path counting problems. After doing several configurations of streets, she decided to come up with a problem of her own. She presented a $3 \times 3$ gridwork of two-way streets (forming 4 blocks in a $2 \times 2$ arrangement) and added the condition that a street could be traversed at most once. She asked how many such paths are there from upper left to lower right? (Answer: 16.)

Stirred by her enthusiasm, we tried generalizing in various directions. If you have 2 long horizontal streets with $N$ verticals, and let $a_N$ be the number of edge-disjoint paths from upper left to lower right and $b_N$ be the number of edge-disjoint paths from upper left to upper right, then $a_{N+1} = b_{N+1} = a_N + b_N$ for $N > 1$ and $a_1 = b_1 = 1$.

The $3 \times N$ case is trickier, but the number of edge-disjoint paths from upper left to lower right still satisfies a finite linear recurrence relation.

Naturally, I turned to OEIS and found sequences A013991-A013997, where Dan Hoey gives the number of edge-disjoint paths between opposite corners of $K \times N$ grids for $K = 3, 4, 5, ..., 9$ and small $N$. He also provides the first few values for the $N \times N$ cases (sequence A013990). (Note, his numbering counts blocks, not streets.) For $K=3$, he provides a generating function. In a recent communication, he explained the computer algorithm he used to compute the values but indicates that he did not find a recurrence relation for these sequences, so as far as I know, there is no known way to determine the answer to the title question for large $N$.

I've also spoken with Gregg Musiker, Bjorn Poonen, and Tim Chow about this problem. Although none knew how to do the $4 \times N$ case, Gregg simplified my recurrence relations for the $3 \times N$ case, Bjorn suggested many related questions and suggested an asymptotic formula for the $N \times N$ case, and Tim suggested looking at the related literature on self-avoiding walks, such as the book by Neal Madras and Gordon Slade, though it's not clear to me how related edge-disjoint and self-avoiding are with respect to counting them.

Because there are finite linear recurrence relations for the $2 \times N$ and $3 \times N$ cases, it seems natural to also ask:

Is there a finite linear recurrence relation for the number of edge-disjoint paths between opposite corners of a $4 \times N$ gridwork of streets?

Are these problems intractable?

Answer 1

To amplify on Christian's answer, the problem on a $K \times N$ grid for fixed $K$ and varying $N$ admits a finite-state transition model, so in particular is given by a linear recurrence.

The key is to find the right set of states. If you take an edge-disjoint path on a $K \times N$ grid and slice it on a vertical line through the middle passing through a set of horizontal edges, you'll see the path crossing along some odd number of these edges ($\le K$). On both the left and right we'll see a collection of paths with these endpoints. There's another constraint, that we end up with a single, connected path without disjoint loops; to take that in to account, also record a matching: which endpoints are paired up on the right hand side. All but one of the endpoints are paired up in this way. (You could also choose the left, and end up with a slightly different matrix.)

For instance, in the $3 \times N$ case, there are $6$ states. If we record an occupied edge by $\times$ and an unoccupied edge by $\circ$ and turn everything on its side, the states are $$ \times\circ\circ\quad\circ\times\circ\quad\circ\circ\times\quad\times_1\times_1\times \quad\times_1\times\times_1\quad\times\times_1\times_1 $$ where the subscript indicates the matching. (In this case, there is at most one matched pair.)

Next consider the transitions. If you consider two adjacent vertical slicings of a path, you'll see two possibly different states. The set of edges that are occupied in the middle is determined by which edges are occupied in the two different states. There is sometimes a choice about how the strands are connected up. However, some of these choices will be ruled out by the constraints on the connectivity; usually you will end up with just $0$ or $1$ possibilities.

For instance, in the $3 \times N$ case, with the states in the order above, I get the following matrix of possibilities: $$ M =\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} $$

For the ultimate answer, you want to look at paths that start at the upper-left and go to the lower-right. You can incorporate that nicely by adding an extra slice to the left of the entire diagram, with only the top slot occupied, and another to the right of the diagram, with only tho lower slot occupied.

Concretely, in the $3 \times N$ case, the number of paths is given by the $(1,3)$ entry of $M^N$.

For the $4 \times N$ case, you would get a $16 \times 16$ matrix, which is straightforward but somewhat tedious to work out. As a result, the answer will satisfy a linear recurrence of order $16$.

An interesting variation is to consider only crossingless paths. In this case, the matching must be crossingless, so we only get 5 states in the $3 \times N$ case and $12$ in the $4 \times N$ case.

Update Jan 7: The matrix above is wrong: it should be $$ M =\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 2 & 2 & 2\\ 1 & 1 & 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} $$

Update 2: And here's an image illustrating what is actually being counted: I permuted the entries slightly, but they're labelled along the sides. The dotted paths are there to help in the counting: the non-allowed configurations would form a closed loop.

Answer 2

Let $v_1$, $\ldots$, $v_N$ be the vertical streets and let $h_{1,j}$, $\ldots$, $h_{4,j}$ be the horizontal edges between $v_{j-1}$ and $v_j$. An admissible path $\gamma$ induces a coloring of the horizontal edges as follows: Consider a vertical street $v_j$. The path $\gamma$ uses either one or three of the incoming edges $h_{k,j}$ $(1\le k\le 4)$. If $\gamma$ uses one edge, color it black and the three other edges white. If $\gamma$ uses three edges, two of them are linked to each other by a part of $\gamma$ extending only to the left of $v_j$. Color these two edges red, the third edge black and the unused edge white. In all, there are 16 possible colorings $c:\lbrace 1,2,3,4\rbrace\to\lbrace b, r, w\rbrace$ that can result in this way. There is a $16\times 16$ transition matrix $T$ that encodes the possible matchings between the coloring $c$ of the edges $h_{k,j}$ and the coloring $c'$ of the edges $h_{k,j+1}$ (e.g., circles must be avoided). This matrix $T$ has to be determined "the hard way", i.e., by listing for each $c$ the possible $c'$. The number of admissible paths $\gamma$ is then obtained by applying $T^{N-1}$ to a suitable starting vector; so there is indeed a linear recurrence for the number of these paths.

An example: If $c$ contains one black and two red edges, then using the vertical edges on $v_j$ in an admissible way one may

(a) continue the black and the two red edges into the next column individually, maybe at a different level,

or

(b) connect the black end of $c$ to either one of the red ends by a vertical segment creating a $\supset$ and continue the other red edge of $c$ into the next column, but as a black edge,

and, if room on $v_j$ permits, one may

(c) throw in two red edges beginning on $v_j$ which are connected by a vertical segment creating a $\subset$.

Here is a pictorial list (hopefully complete) of the possible transitions $c\to c'$:

http://www.math.ethz.ch/~blatter/grid.pdf