Given $n$ colours, find the number of ways to colour an $n \times n$ grid such that no row or column contains the same colour.
My motivation for this problem arises from a version of this problem I came across for the case $n = 3$.
My solution:
Consider a permutation of the $n$ colours to fill the first row. We now seek derangements of the permutation for the rows below. At each succeeding row, however, an extra derangement will be used up. Representing the number of derangements of $n$ elements to be $d_n$ and considering all the possible orderings of the first-row permutation, we can find a general representation for the desired number of ways as follows:
$$n! \times d_n \times (d_n – 1) \times (d_n – 2) \, \times \, … \, \times \, (d_n – (n – 2))$$
$$ = \frac{n!d_n!}{(d_n – n + 3)!} \quad \text{where} \quad d_n = n!\sum_{r = 0}^n\frac{(-1)^r}{r!}$$
My question:
- Is my solution correct?
- Are there alternate solutions?
Best Answer
The solution is not correct. The third factor must be smaller than $d_n-1$ in general, since there are more derangements than just the second row that nonetheless would share colors with it.
Say we refer to colors by numbers. If the first row is $(1234)$ and the second row is $(2143)$ then the third row must be a different derangement, but it also can't be $(4123)$ for example, even though that's a derangement of the first row that's different from the second row. And so on for all the other factors, so the formula you found will in general be greatly overcounting the grid colorings.
In fact, if the first row is $(1234)$, then the number of options for the third row depends on what the second row is. If the second row is $(2143)$ then there are four options for the third row, whereas if the second row is $(2341)$ then there are only two options for the third row. Thus, the problem can't be a simple as multiplying the numbers of options for each row together. Write out the eight derangements of $(1234)$ and verify my statements as an exercise.
You're asking about Latin squares. There are asymptotics, but no easily-computable formulas, counting them.