# $n$ permutations in $S_n$, no two of which agree on any point

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.

• the sudoku analogy is perfect
– D S
Dec 7, 2022 at 17:13
• 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.
– D S
Dec 7, 2022 at 17:16

## 1 Answer

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