Question 30
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)}$.
- $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)}$.