10
$\begingroup$

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

$\endgroup$
10
  • 1
    $\begingroup$ If we consider the analogous problem with two rows, we are computing the number of derangements, a classic problem (with a well-known solution). I ask those voting to close: is the case for three rows a straightforward extension of this problem? $\endgroup$
    – Todd Trimble
    Oct 15, 2013 at 15:40
  • 2
    $\begingroup$ The question is certainly poorly stated, but I don't think that it is totally off-topic. Indeed, as Todd Trimble remarks, the question is: Let $\sigma$ be a fixed-point-free permutation. What is the number of fixed-point-free permutations $\tau$ such that $\sigma^{-1}\tau$ is fixed-point-free too? This number depends on $\sigma$ (as the OP remarked already). I only see how to compute this number via the character table of the symmetric group $S_N$. $\endgroup$ Oct 15, 2013 at 15:48
  • 1
    $\begingroup$ Yes, it's not exactly stated in a professional manner, but the problem could probably be rephrased to make it "MO-worthy". If you have a solution, @PeterMueller, it might be worth putting down (albeit it quickly! since the question looks doomed for closure at this rate). $\endgroup$
    – Todd Trimble
    Oct 15, 2013 at 15:52
  • 1
    $\begingroup$ More naturally, this is counting Latin rectangles with the first two rows specified. It strikes me as a kind of "Project Euler" problem, and one might take care before responding. (See a post on meta talking about not answering such problems.) Gerhard "Off To Do Some Writing" Paseman, 2013.10.15 $\endgroup$ Oct 15, 2013 at 20:30
  • 4
    $\begingroup$ As I recall, this problem is discussed in Riordan's Introduction to Combinatorial Analysis, but I don't have my copy handy. You might also be able to find some relevant references by searching for "discordant permutations". On another aspect of the question, although the number of possible $\tau$ depends on $\sigma$, this number is close to $n!/e^2$ independently of $\sigma$. Stronger asymptotic results on the number of ways to add a row to a Latin rectangle can be found in C. D. Godsil, and B. D. McKay, Asymptotic enumeration of Latin rectangles. J. Combin. Theory Ser. B 48 (1990), 19–44. $\endgroup$
    – Ira Gessel
    Oct 16, 2013 at 19:53

5 Answers 5

14
$\begingroup$

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.

$\endgroup$
2
  • 7
    $\begingroup$ Maybe one should make clear that this does not answer the question, unless the conjugacy class of $\sigma$ is already determined by the number $j$ of cycles. $\endgroup$ Oct 16, 2013 at 8:59
  • $\begingroup$ Peter, you are correct; I missed this nuance when I first posted the answer. The number I described only gives the average over all permutations with $j$ cycles. $\endgroup$ Oct 17, 2013 at 1:01
8
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.