CMO 2008 Problem 5

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$.