Denote the set of $n\times n$ permutation matrices by $\mathfrak{S}_n$. The ordinary transpose preserves this group.
Given $P\in\mathfrak{S}_n$, construct the $n\times n$ matrix ${}^tP$ according to the rules:
(1) leave the 4 rims unchanged (1st row, 1st column, last row, last column);
(2) transpose its $(n-2)\times(n-2)$-submatrix found by removing the 4 rims.
Example. $$A=\begin{pmatrix} 1&0&0&0\\0&0&0&1\\0&1&0&0\\0&0&1&0 \end{pmatrix} \rightarrow {}^tA=\begin{pmatrix} 1&0&0&0\\0&0&1&1\\0&0&0&0\\0&0&1&0 \end{pmatrix}.$$ Example. $$B=\begin{pmatrix} 1&0&0&0\\0&0&0&1\\0&0&1&0\\0&1&0&0 \end{pmatrix} \rightarrow {}^tB=\begin{pmatrix} 1&0&0&0\\0&0&0&1\\0&0&1&0\\0&1&0&0 \end{pmatrix}.$$ Notice that ${}^tB$ is a permutation while ${}^tA$ is not!
Question. What is $a_n:=\#\{^{t}P\in\mathfrak{S}_n:\,\,P\in\mathfrak{S}_n\}$, for $\geq3$? Easy: $a_3=6$.
Remark. This was a modest case (see answer below). We could easily generalize the problem in many ways.
Question 2. Split $P=\begin{pmatrix}A&B\\C&D\end{pmatrix}\in\mathfrak{S}_{2n}$ into four $n\times n$ matrices, and define the operation ${}^{tt}P=\begin{pmatrix}{}^tA&{}^tB\\ {}^tC&{}^tD\end{pmatrix}.$ How many involutions are there in $\mathfrak{S}_{2n}$ such that $^{tt}P$ is a permutation?
