HMMT 2012 T10

For positive odd integer $n$, let $f(n)$ denote the number of matrices $A$ satisfying the following conditions:

• $A$ is $n \times n$.
• Each row and column contains each of $1,2, \ldots, n$ exactly once in some order.
• $A^{T}=A$. (That is, the element in row $i$ and column $j$ is equal to the one in row $j$ and column $i$, for all $1 \leq i, j \leq n$.) Prove that $f(n) \geq \frac{n!(n-1)!}{\varphi(n)}$.