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.

Answer 2

To complement Timothy Chow's nice answer, here's a recent and great survey on this topic if anyone is interested:

D. S. Stones, The Many Formulae for the Number of Latin Rectangles, Electron. J. Combin. 17 (2010) #A1

A $k×n$ Latin rectangle $L$ is a $k×n$ array, with symbols from a set of cardinality $n$, such that each row and each column contains only distinct symbols. If $k=n$ then $L$ is a Latin square. Let $L_{k,n}$ be the number of $k×n$ Latin rectangles. We survey (a) the many combinatorial objects equivalent to Latin squares, (b) the known bounds on $L_{k,n}$ and approximations for $L_{n}$, (c) congruences satisfied by $L_{k,n}$ and (d) the many published formulae for $L_{k,n}$ and related numbers. We also describe in detail the method of Sade in finding $L_{7,7}$, an important milestone in the enumeration of Latin squares, but which was privately published in French. Doyle's formula for $L_{k,n}$ is given in a closed form and is used to compute previously unpublished values of $L_{4,n}$, $L_{5,n}$ and $L_{6,n}$. We reproduce the three formulae for $L_{k,n}$ by Fu that were published in Chinese. We give a formula for $L_{k,n}$ that contains, as special cases, formulae of (a) Fu, (b) Shao and Wei and (c) McKay and Wanless. We also introduce a new equation for $L_{k,n}$ whose complexity lies in computing subgraphs of the rook's graph.

OP's question is asking a formula for $L_{3,n}$. The paper Timothy Chow mentioned is available for free from the author's website:

http://people.brandeis.edu/~gessel/homepage/papers/3latin.pdf

Answer 3

Let $\sigma\in S_n$ be a derangement. The question asks for the number of derangements $\tau,\rho$ such that $\sigma\tau\rho=1$. Fix $\tau', \rho'\in S_n$. The number of pairs $\tau,\rho$ with $\sigma\tau\rho=1$, $\tau$ conjugate to $\tau'$, and $\rho$ conjugate to $\rho'$, is \begin{equation} \frac{1}{n!}\lvert C(\tau')\rvert\cdot\lvert C(\rho')\rvert\sum_{\chi}\frac{\chi(\sigma)\chi(\tau')\chi(\rho')}{\chi(1)}, \end{equation} where $\chi$ runs through the irreducible characters of $S_n$, and $C(\beta)$ is the conjugacy class of $\beta$. This formula is well known, maybe most prominently in the context of the rigidity criterion of inverse Galois theory.

All we need to do now is to let $\tau'$ and $\rho'$ run through the conjugacy classes representatives of the derangements, and some up the terms.

So the number the OP asks for is \begin{equation} \frac{1}{n!}\sum_{\chi}\frac{\chi(\sigma)}{\chi(1)}\left(\sum_{\tau'}\chi(\tau')\lvert C(\tau')\rvert\right)^2, \end{equation} where $\tau'$ runs through the representatives of the derangements.

I don't know if this expression can be simplified. Note that if $\chi\ne1$, then $\sum_{\beta\in S_n}\chi(\beta)=0$ by orthogonality. So we may also let run $\tau'$ through the representatives of elements with at least one fixed point.

As is well known, the conjugacy classes of $S_n$ are parametrized by the partitions of $n$, and so are the irreducible characters. With regard to this parametrization, the character values can be computed, see e.g. this nice exposition (without proofs).

Answer 4

A formula for the answer to this question is given in formula (3) of J. Riordan, Three-line Latin rectangles, Amer. Math. Monthly 51, (1944), 450–452. Riordan doesn't really include a proof, though it's not too hard to see how the formula follows from the theory of rook polynomials. (He refers to a paper of Kaplansky, but Kaplansky's paper doesn't have this formula.)

I believe that Riordan also discusses this problem in his book Introduction to Combinatorial Analysis, but I didn't check.

Answer 5

Let me copy here an answer from Russian forum dxdy.ru that I obtained using the approach outlined in my paper.

Two given rows of a $3\times N$ matrix define a permutation of order $N$. Let $c_i$ ($i=1,2,\dots,N$) be the number of cycles of length $i$ in this permutation (in particular, $c_1$ is the number of fixed points, which is 0 iff given permutations form a derangement).

Then the number of different third rows that form derangements with respect to each of the first two rows equals $$\sum_{j=0}^n (-1)^j\cdot (n-j)!\cdot [z^j]\ F(z),$$ where $[z^j]$ is the operator of taking the coefficient of $z^j$ and $$F(z) = (1+z)^{c_1}\cdot \prod_{i=2}^n \left( \left(\frac{1+\sqrt{1+4z}}2\right)^{2i} + \left(\frac{1-\sqrt{1+4z}}2\right)^{2i} \right)^{c_i}.$$

Particular cases:

• For $c_1=n$ (i.e., two given rows are equal), we get just the number derangements.
• For $c_n=1$, we get menage numbers A000179(n).
• For $n=2m$ and $c_2=m$, we get A000316(m) = A000459(m)$\cdot 2^m$.

This question inspired me to add the following new sequences to the OEIS: A277256, A277257, and A277265.