1
$\begingroup$

Q: How many tuples of permutations ($\sigma_1$,..$\sigma_n$), $\sigma_i \in S_n$ have the property that no two of them agree on any element?

This is sort of a generalization of derangements, but I feel like there should be a way to think about the problem which is not just "derangements, but more complictated." Some intuition for this is that $n$ permutations in $S_n$ is an extremal condition for this property.

I see that this is equivalent to the number of Sudoku puzzles without the subsquare conditions. I couldn't find more about this in the literature.

I would also be happy with a asymptotic solution, like derangements.

$\endgroup$
2
  • 1
    $\begingroup$ the sudoku analogy is perfect $\endgroup$
    – D S
    Dec 7, 2022 at 17:13
  • $\begingroup$ consider that you have a $n \times n$ sudoku grid, and you fill it in such a way that every row is a permutation of the given set, and every element occurs once in a column. Then, to add a $n+1$ th row, at least 1 column will have an element repeated twice. $\endgroup$
    – D S
    Dec 7, 2022 at 17:16

1 Answer 1

4
$\begingroup$

A tuple of $n$ permutations, no two of which agree at any place, is exactly a Latin Square.

Letting $L_n$ be the number of Latin squares, there is no formula for $L_n$. We know the following inequalities: $$ \frac{(n!)^{2n}}{n^{n^2}}\le L_n\le \prod_{k=1}^n (k!)^{n/k}. $$ The ratio between these two bounds grows like $n^{n/2}$, so is somewhat loose. At least we can approximate $\log L_n$ reasonably well: $$ \log L_n= n^2\log n -2n^2 + O(n\log n). $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .