¿De cuántas maneras diferentes podemos colocar N torres idénticas en un tablero de ajedrez SIN ESQUINAS de modo que no se ataquen dos de ellas (para N > 3)?

La primera observación es que hay exactamente una torre en cada fila. Entonces, contemos el número de formas de colocar torres en la primera y última fila. Hay$N-2$casillas para elegir y una vez que colocamos la primera torre, quita exactamente una opción para colocar la segunda torre, por lo que hay$(N-2)(N-3)$opciones Ahora elimine las filas y columnas que ocupan estas torres y nos queda colocar$N-2$torres en un tablero cuadrado de tamaño$N-2$. Hay$(N-2)!$maneras de hacer esto (discutir esto colocando torres fila por fila). Entonces en total hay$(N-2)(N-3)[(N-2)!]$Formas de colocar las torres.

Cuando N=8, esto da 6*5*(6!) = 21600 formas.

Dejar$A_{(x,y)}$Sea el número de ubicaciones de$N$torres en un$M\times M$tablero de ajedrez con una torre en cuadrado$(x,y)$entonces queremos contar las posiciones de torres que no pertenecen a ninguno de$A_{(1,1)}$,$A_{(1,M)}$,$A_{(M,1)}$o$A_{(M,M)}$para que podamos usar$\xi$para representar el conjunto de todas las ubicaciones de$N$torres en nuestro$M\times M$tablero entonces

$$|\xi|= \binom{M}{N}^2N!$$

porque elegimos$N$filas de$M$en el que colocar nuestras torres$\binom{M}{N}$Luego haga una selección ordenada de$N$columnas de$M$en$\binom{M}{N}N!$maneras.

A continuación tenemos

$$|A_{(x,y)}|=\binom{M-1}{N-1}^2(N-1)!$$

por el mismo argumento, solo que esta vez hemos colocado una torre en celda$(x,y)$que deja$M-1$filas y columnas en las que colocar el resto$N-1$torres Hay$4$tales conjuntos, uno para cada esquina de la$M\times M$junta.

Entonces nosotros tenemos

$$|A_{(x_1,y_1)}\cap A_{(x_2,y_2)}|=\begin{cases}& 0\qquad &x_1= x_2,\, \text{or}\, y_1= y_2\\& \dbinom{M-2}{N-2}^2(N-2)!\qquad &\text{else}\end{cases}$$

Ya que solo hay$2$intersecciones distintas de cero$A_{(1,1)}\cap A_{(M,M)}$y$A_{(1,M)}\cap A_{(M,1)}$y no puede haber$3$-intersecciones entonces tenemos por el principio de inclusión-exclusión

$$\begin{align}\text{Desired count}&=|\xi|-(|A_{(1,1)}|+|A_{(1,M)}|+|A_{(M,1)}|+|A_{(M,M)}|) + (|A_{(1,1)}\cap A_{(M,M)}|+|A_{(1,M)}\cap A_{(M,1)}|)\\ &=\binom{M}{N}^2N!-4\binom{M-1}{N-1}^2(N-1)!+2\binom{M-2}{N-2}^2(N-2)!\end{align}$$

Según sea necesario.

También es posible usar polinomios de torre para esto, pero tal vez sea desconocido para muchos, por lo tanto, el enfoque anterior.

Este problema se puede resolver convenientemente usando polinomios de torre . Podemos intercambiar filas y columnas por pares sin cambiar el número de arreglos posibles de las torres no atacantes. A continuación se muestra una placa equivalente.

                                                                

El polinomio de la torre de los cuatro cuadrados prohibidos en la esquina superior izquierda es

$$\begin{align*} 1+4x+2x^2\tag{1} \end{align*}$$ donde el coeficiente de$x^k$da el número de maneras de colocar$k$torres no atacantes en las casillas prohibidas. El número de arreglos válidos para colocar ocho torres no atacantes en el$(8\times 8)$tablero con respecto a las casillas prohibidas está dada por (1) usando el principio de inclusión-exclusión como $$\begin{align*} 1\cdot 8!-4\cdot 7!+2\cdot 6!\color{blue}{=21\,600} \end{align*}$$ Podemos colocar ocho torres no atacantes en$8!$formas, restar$4\cdot7!$formas que tienen al menos una torre en una de las cuatro casillas prohibidas y se suman como compensación por la doble contabilidad$2\cdot6!$formas que tienen dos torres no atacantes en las cuatro casillas prohibidas.