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