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\}$?
$\begingroup$
$\endgroup$
4
-
7$\begingroup$ Such objects are called Latin squares. $\endgroup$– Michael AlbertMar 25, 2014 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 MyersonMar 25, 2014 at 2:06
-
$\begingroup$ No effective general formula or even the asymptotic behaviour is known. $\endgroup$– Brendan McKayMar 25, 2014 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 DukesMar 25, 2014 at 22:58
Add a comment
|