Torres no atacantes con simetría en ambas diagonales

Question

Esta es la pregunta:

Dejemos que $T_{n}$ denotan el número de formas de colocar $n$ torres no atacantes en un $n×n$ tablero de ajedrez para que la disposición resultante sea simétrica respecto a ambas diagonales. Calcule $T_{n}$ .

Ya me he enfrentado a algunos de estos problemas de torres no atacantes y he podido resolverlos en su mayor parte, pero este me está dando algunos problemas.

Algo que he notado es que cuando n es par, cada colocación de una torre define una o tres otras colocaciones de la torre, lo que significa que si un número tiene la forma 4n+2, entonces al menos una torre está en una de estas diagonales (es decir, sólo genera otra colocación de la torre). No estoy seguro de cómo usar esto, o si es útil.

Se agradece cualquier ayuda.

Answer 1

Si observa que este es el mismo problema que contar gráficos bipartitos que representan permutaciones y que tienen simetría de espejo vertical y horizontal. Es más fácil derivar la recursión de esta manera. Obtengo para $n\in\mathbb{N}\cup\{0\}$ :

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

y

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

con $T_0=1,T_1=1,T_2=2,T_3=2$ podemos generar el resto de la secuencia

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

la comprobación de esto en la oeis da como resultado esta secuencia que tiene mucha más información.

Para derivar la recurrencia anterior basta con observar que para $T_{2n}$ puntos $1$ y $2n$ puede cada uno asignarse a sí mismo o a los demás dejando $2n-2$ puntos a mapear en $T_{2n-2}$ formas, esto da lugar a $2T_{2n-2}$ . Alternativamente $1$ mapas a puntos $k$ y $2n$ mapas a $2n-k$ mientras que los puntos $k$ y $2n-k$ mapa a puntos $1$ y $2n$ respectivamente. Así que $k$ puede tomar valores $2$ a $2n-1$ ( $2n-2$ valores) y en cada caso el resto de $2n-4$ los puntos deben mapearse en $T_{2n-4}$ formas, esto da lugar al término $2(n-1)T_{2n-4}$ .

Los casos impar se razonan de forma similar con la única diferencia de que el punto medio $(2n+3)/2$ siempre se asigna a sí mismo.

Answer 2

Probablemente tengas que hacerlo de forma recursiva.

Suponga que tiene un espacio en blanco $n\times n$ tablero, donde por ahora asumiré $n$ está en paz. Coloca una torre en la primera columna.

Si la colocas en la fila superior o inferior, la simetría diagonal te obliga a poner una torre en la última columna diagonalmente opuesta. Entonces tienes una $(n-2)\times (n-2)$ cuadrado en el centro que se puede rellenar $T_{n-2}$ formas.

Si colocas una torre en la primera columna en cualquier otro lugar, la simetría diagonal te obliga a poner tres torres más en el tablero. Estas torres cubren cuatro filas y cuatro columnas del tablero, dejando una disposición simétrica de $n-4$ filas y $n-4$ columnas a rellenar. ¿De cuántas maneras se puede hacer eso?

Lo anterior le dará una relación recursiva. Junto con el hecho de que $T_2=2$ (y vacuamente $T_0=1$ ) se pueden generar los valores de $T_n$ para incluso $n$ aunque puede ser difícil derivar una fórmula directa para ello.

Averiguar qué pasa cuando $n$ es impar es relativamente fácil.