2
$\begingroup$

Let $\sigma_1,\ldots, \sigma_k$ be permutations of $\{1,2,\ldots,k\}$. I want to determine the number of $k$-tuples $(\sigma_1,\ldots, \sigma_k)$ of permutations such that, for each $1\leq j\leq k$, setting $\sigma^j(i)=\sigma_i(j)$ is also permutation. In other words, letting $M_{i,j}=\sigma_i(j)$, what is the total number of $k\times k$ matrices for which each row and each column represents a permutation of $\{1,2,\ldots, k\}$?

$\endgroup$
  • 7
    $\begingroup$ Such objects are called Latin squares. $\endgroup$ – Michael Albert Mar 25 '14 at 1:37
  • 4
    $\begingroup$ The number of $k\times k$ Latin squares is tabulated at oeis.org/A002860 --- it only goes to $k=11$. $\endgroup$ – Gerry Myerson Mar 25 '14 at 2:06
  • $\begingroup$ No effective general formula or even the asymptotic behaviour is known. $\endgroup$ – Brendan McKay Mar 25 '14 at 8:48
  • $\begingroup$ It is conjectured, I think, that the number of 1-factorizations of $K_n$ is about $(n/e^2)^{n^2/2}$. Bounds are known, but where the base of the exponent differs by a constant multiple. We want 1-factorizations of $K_{n,n}$ instead. Do the techniques extend somehow? With not much effort we get something in between $(C_1 n)^{n^2/2}$ and $(C_2 n)^{2n^2}$, but there is a huge gap. $\endgroup$ – Peter Dukes Mar 25 '14 at 22:58

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy