Explanation for the $\frac{(n!)^{2n}}{n^{n^2}}$ lower bound on the number of Latin squares?

Question

Wikipedia says that there are at least $\frac{(n!)^{2n}}{n^{n^2}}$ Latin squares of size $n$. But the citation is a paywalled textbook. How does one prove this bound?

Answer 1

Here is a sketch of their proof. Build your Latin square one row at a time. At the $k^{th}$ stage, you have a $k\times n$ Latin rectangle, $R_k$. Let us count the number of ways to extend $R_k$ to $R_{k+1}$. This can be computed as the permanent of a certain matrix. Namely, for each $k\in \{0,1,\dots,n-1\}$, define the $n\times n$ matrix $B^k$ by saying $B^k_{i,j}=1$ if the $j^{th}$ column of $R_k$ does not contain the entry $i$. Then the number of ways to extend $R_k$ is $\def\per{\text{per }}\per B_k$. Therefore, $$ \text{# $n\times n$ Latin squares} \ge \prod_{k=0}^{n-1}. \per B_k\tag1 $$ Finally, you can show that $\frac{1}{n-k} B_k$ is a doubly stochastic matrix, which by Van der Waerden's conjecture implies $\per \!\!\left(\frac{1}{n-k}B_k\right)\ge n!/n^n$, or $$\per B_k \ge (n-k)^n n!/n^n.\tag 2$$ Combining $(1)$ and $(2)$ gives you what you want.