The question asks for the number of reduced three-line Latin rectangles with prescribed second row. The best answer I know of is the following result due to Ira Gessel (<i>Combinatoire énumérative</i>,
Lecture Notes in Mathematics Volume 1234, 1986, pp.106–111):
><b>Theorem</b>. The number of pairs $(\sigma,\tau)$ of permutations of
$\lbrace 1, 2, \ldots, n\rbrace$ such that $\sigma$, $\tau$, and $\sigma\tau^{-1}$
are fixed-point-free, $\sigma$ has $j$ cycles, and $\tau$ has $k$ cycles is the coefficient
of $\alpha^j\beta^k x^n\!/n!$ in
$$e^{2\alpha\beta x} \sum_{n=0}^\infty {\alpha^{\bar n}\beta^{\bar n}\over n!}
{x^n \over (1+\alpha x)^{n+\beta} (1+\beta x)^{n+\alpha}(1+x)^{n+\alpha\beta}},$$
where $\alpha^{\bar n} := \alpha(\alpha+1)\cdots(\alpha+n-1)$.
Since we only care about the total number of $\tau$ for a given $\sigma$, we can set $\beta=1$ and just extract the coefficient of $\alpha^j x^n\!/n!$ and divide by the (unsigned) Stirling number of the first kind, $|s(n,j)|$.
<hr>
<b>Edit:</b> As pointed out in the comments below, the above formula does not quite answer the question as stated. Following Ira Gessel's suggestion, I checked out Riordan's book, and indeed Riordan addresses this problem in Chapter 8, Section 3, Theorem 2. However, Riordan's Theorem 2 does not give an explicit formula as such, and he comments that "Formal expressions for specific classes are too involved to be written out in any but the simplest cases." One such case is when $\tau$ is a single cycle (relative to $\sigma$), which corresponds to the famous <a href="http://en.wikipedia.org/wiki/M%C3%A9nage_problem">ménage problem</a>.