[Math] Number of Permutations

Question

Edit: This is a modest rephrasing of the question as originally stated below the fold: for $n \geq 3$, let $\sigma \in S_n$ be a fixed-point-free permutation. How many fixed-point-free permutations $\tau$ are there such that $\sigma \tau^{-1}$ is also fixed-point free? As the original post shows, this number is a function of $\sigma$; can one give a formula based on the character table of $S_n$?

---

Given two permutation of $1, \ldots, N$. Where $3\le N\le 1000$
Example

For $N=4$

First is $\begin{pmatrix}3& 1& 2& 4\end{pmatrix}$.

Second is $\begin{pmatrix}2& 4& 1& 3\end{pmatrix}$.

Find the number of possible permutations $X_1, \ldots, X_N$ of $1, \ldots, N$
such that if we write all three in $3\times N$ matrix, each column must have unique elements.

$\begin{pmatrix}3 & 1 & 2 & 4\\
2 & 4 & 1 & 3\\
X_1 & X_2 & X_3 & X_4\end{pmatrix},$

here
$X_1$ can't be 3 or 2,
$X_2$ can't be 1 or 4,
$X_3$ can't be 2 or 1,
$X_4$ cant be 4 or 3,

Answer to above sample is 2
and possible permutation for third row is $\begin{pmatrix}1 & 3 & 4 & 2\end{pmatrix}$ and $\begin{pmatrix}4 & 2 & 3& 1\end{pmatrix}$.

Example 2

First is $\begin{pmatrix}2 & 4 & 1 & 3\end{pmatrix}$.

Second is $\begin{pmatrix}1 & 3 & 2 & 4\end{pmatrix}$.

Anwser is 4.
Possible permutations for third row are $\begin{pmatrix}3&1&4&2\end{pmatrix}$, $\begin{pmatrix}3&2&4&1\end{pmatrix}$, $\begin{pmatrix}4&1&3&2\end{pmatrix}$ and $\begin{pmatrix}4&2&3&1\end{pmatrix}$.

Answer 1

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 (Combinatoire énumérative, Lecture Notes in Mathematics Volume 1234, 1986, pp.106–111):

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

---

Edit: 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 ménage problem.