## Return to Answer

3 added 135 characters in body

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 a 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

2 added a paragraph

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 looking at all 256 cases. 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 a 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$.

1

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 looking at all 256 cases. 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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 102, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9043135046958923, "perplexity_flag": "head"}