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

5more comments