Non Attacking Rooks With Symmetry On Both Diagonals

Question

Here is the question:

Let $T_{n}$ denote the number of ways of placing $n$ non-attacking rooks on an $n×n$ chessboard so that the resulting arrangement is symmetric about both diagonals. Compute $T_{n}$.

I've dealt with some of these non-attacking rook problems before and have been able to work these out for the most part, but this one is giving me some trouble.

Something I've noted is that when n is even, every placement of a rook defines one or three other rook placements, meaning that if a number has form 4n+2, then at least one rook is on one of these diagonals (ie it only generates one other rook placement). I'm not sure how to use this, or if it is even useful.

Any help is much appreciated!

Answer 1

If you notice that this is the same problem as counting bipartite graphs that represent permutations and which have vertical and horizontal mirror symmetry. It is easier to derive the recursion this way. I get for $n\in\mathbb{N}\cup\{0\}$:

$$T_{2n}=2T_{2n-2}+2(n-1)T_{2n-4}$$

and

$$T_{2n+1}=2T_{2n-1}+2(n-1)T_{2n-3}$$

with $T_0=1,T_1=1,T_2=2,T_3=2$ we can generate the rest of the sequence

$$1,1,2,2,6,6,20,20,76,76,\ldots$$

checking for this on oeis yields this sequence which has plenty more information.

To derive the recurrence above simply note that for $T_{2n}$ points $1$ and $2n$ can each map to themselves or each other leaving $2n-2$ points to map in $T_{2n-2}$ ways, this gives rise to $2T_{2n-2}$. Alternatively $1$ maps to points $k$ and $2n$ maps to $2n-k$ whilst points $k$ and $2n-k$ map to points $1$ and $2n$ respectively. So $k$ may take on values $2$ to $2n-1$ ($2n-2$ values) and in each case the remaining $2n-4$ points must map in $T_{2n-4}$ ways, this gives rise to the term $2(n-1)T_{2n-4}$.

The odd cases are reasoned similarly with the only difference being that the middle point $(2n+3)/2$ always maps to itself.

Answer 2

You probably have to do it recursively.

Suppose you have a blank $n\times n$ board, where for now I'll assume $n$ is even. Place a rook in the first column.

If you place it in the top or bottom row, the diagonal symmetry forces you to put a rook in the last column diagonally opposite. You then have an $(n-2)\times (n-2)$ square in the middle that can be filled in $T_{n-2}$ ways.

If you place a rook in the first column anywhere else, then the diagonal symmetry forces you to put three more rooks on the board. These rooks cover four rows and four columns of the board, leaving a symmetric arrangement of $n-4$ rows and $n-4$ columns to be filled. In how many ways can that be done?

The above will give you a recursive relation. Together with the fact that $T_2=2$ (and vacuously $T_0=1$) you can then generate the values of $T_n$ for even $n$, though it might be difficult to derive a direct formula for it.

Figuring out what happens when $n$ is odd is relatively easy.