Problem: Let $S$ be a $n \times 3$ chessboard. Let a rook walk on the board, it is allowed to move $1$ step horizontally or vertically every step. Determine the number of ways the rook can go from the bottom left corner $(1,1)$ to the bottom right corner $(n,1)$ such that the rook has been on every square of the board exactly once (so in this context $(1,1)$ is a square for example)
My question: I don't know how start start in a structured manner for this one. Can anyone help me/give me tips or the full solution? Thanks in advance
Hint It is an intuition, but for topological reasons, it seems to me that the simplest way to go from $(1, 1)$ to $(n, 1)$ is to follow the pattern \begin{equation} R^{k-1} U L^{k-1} U R^{n-1} D L^{n-k-1} D R^{n-k-1} \end{equation} where $1\le k\le n-1$ and $R, U, L, D$ mean go right, up, left, down respectively. Let us call this pattern $P_{n, k}$.
It seems reasonable to think that the only way to go from $(1, 1)$ to $(n, 1)$ is a composition of the form \begin{equation} P_{n_1, k_1} R P_{n_2, k_2} R\cdots R P_{n_j, k_j} \end{equation} where $n_1 + n_2 + \cdots + n_j = n$. If this is true, the number of ways to go from $(1,1)$ to $(n, 1)$ would be \begin{equation} N(n) =\sum_{n_1+\cdots+n_j = n\atop n_i\ge 2}(n_1-1)\cdots(n_j-1) \end{equation} Numerical investigations as well as a proof in the comments below indicate that this summation $N(n)$ reduces to $2^{n-2}$ as claimed by @Batominovski and @BrianMoehring