A self-avoiding rook walk on a chessboard (a rectangular grid of squares) is a path traced by a sequence of rook moves parallel to an edge of the board from one unit square to another, such that each begins where the previous move ended and such that no move ever crosses a square that has previously been crossed, i.e., the rook's path is non-self-intersecting.

Let $R(m, n)$ be the number of self-avoiding rook walks on an $m \times n$ ( $m$ rows, $n$ columns) chessboard which begin at the lower-left corner and end at the upper-left corner. For example, $R(m, 1)=1$ for all
natural numbers $m ; R(2,2)=2 ; R(3,2)=4 ; R(3,3)=11$. Find a formula for $R(3, n)$ for each natural number $n$.
Employ the same notation as in Solution 1. We have that \( r_{1}=1, r_{2}=4 \) and \( r_{3}=11 \). Let \( n \geq 3 \). Consider the situation that there are \( r_{n+1} \) columns. There are basically three types of rook walks.

Type 1. There are four rook walks that enter only the first two columns.

Type 2. There are \( 3 r_{n-1} \) rooks walks that do not pass between the second and third columns in the middle row (in either direction), viz. \( r_{n-1} \) of each of the types:

\[
\begin{gathered}
(1,1) \longrightarrow(1,2) \longrightarrow(1,3) \longrightarrow \cdots \longrightarrow(3,3) \longrightarrow(3,2) \longrightarrow(3,1) ; \\
(1,1) \longrightarrow(2,1) \longrightarrow(2,2) \longrightarrow(1,2) \longrightarrow(1,3) \longrightarrow \cdots \longrightarrow(3,3) \longrightarrow(3,2) \longrightarrow(3,1) ; \\
(1,1) \longrightarrow(1,2) \longrightarrow(1,3) \longrightarrow \cdots \longrightarrow(3,3) \longrightarrow(3,2) \longrightarrow(2,2) \longrightarrow(2,1) \longrightarrow(3,1) .
\end{gathered}
\]

Type 3. Consider the rook walks that pass between the second and third column along the middle row.

They are of Type 3a:

\[
(1,1) \longrightarrow * \longrightarrow(2,2) \longrightarrow(2,3) \longrightarrow \cdots \longrightarrow(3,3) \longrightarrow(3,2) \longrightarrow(3,1) \text {, }
\]

or Type \( 3 b \):

\[
(1,1) \longrightarrow(1,2) \longrightarrow(1,3) \longrightarrow \cdots \longrightarrow(2,3) \longrightarrow(2,2) \longrightarrow * \longrightarrow(3,1) \text {, }
\]

where in each case the asterisk stands for one of two possible options.

We can associate in a two-one way the walks of Type 3a to a rook walk on the last \( n \) columns, namely

\[
(1,2) \longrightarrow(2,2) \longrightarrow(2,3) \longrightarrow \cdots \longrightarrow(3,3) \longrightarrow(3,2)
\]

and the walks of Type \( 3 \mathrm{~b} \) to a rook walk on the last \( n \) columns, namely

\[
(1,2) \longrightarrow(1,3) \longrightarrow \cdots \longrightarrow(2,3) \longrightarrow(2,2) \longrightarrow(3,2) \text {. }
\]

The number of rook walks of the latter two types together is \( r_{n}-1-r_{n-1} \). From the number of rook walks on the last \( n \) columns, we subtract one for \( (1,2) \rightarrow(2,2) \rightarrow(3,2) \) and \( r_{n-1} \) for those of the type

\[
(1,2) \longrightarrow(1,3) \longrightarrow \cdots \longrightarrow(3,3) \longrightarrow(2,3) \text {. }
\]

Therefore, the number of rook walks of Type 3 is \( 2\left(r_{n}-1-r_{n-1}\right) \) and we find that

\[
r_{n+1}=4+3 r_{n-1}+2\left(r_{n}-1-r_{n-1}\right)=2+2 r_{n}+r_{n-1} .
\]

We can now complete the solution as in Solution 1.