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\}$?

  • 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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.