2005 Putnam A2

Let $\mathbf{S} = \{(a,b) | a = 1, 2, \dots,n, b = 1,2,3\}$.
A *rook tour* of $\mathbf{S}$ is a polygonal path made up of line
segments connecting points $p_1, p_2, \dots, p_{3n}$ in sequence such that

(i) $p_i \in \mathbf{S}$,

(ii) $p_i$ and $p_{i+1}$ are a unit distance apart, for
$1 \leq i <3n$,

(iii) for each $p \in \mathbf{S}$ there is a unique $i$ such that
$p_i = p$. How many rook tours are there that begin at $(1,1)$
and end at $(n,1)$?

(An example of such a rook tour for $n=5$ was depicted in the original.)

设 $\mathbf{S} = \{(a,b) | a = 1, 2, \dots,n, b = 1,2,3\}$。

$\mathbf{S}$ 的 *rooktour* 是一条由直线组成的多边形路径

按顺序连接点 $p_1, p_2, \dots, p_{3n}$ 的线段使得

(i) $p_i \in \mathbf{S}$,

(ii) $p_i$ 和 $p_{i+1}$ 相距单位距离，对于

$1 \leq i <3n$,

(iii) 对于每个 $p \in \mathbf{S}$ 都有一个唯一的 $i$ 使得
$p_i = p$。有多少个以 $(1,1)$ 开始的车之旅
并以 $(n,1)$ 结束？

(原文中描述了 $n=5$ 的此类车巡演的示例。)