Polinomio de torre

Para tableros de n × n de cuadros incompletos, (es decir, no se permite jugar a las torres en algún subconjunto arbitrario de las casillas del tablero) calcular el número de maneras de colocar n torres en el tablero es equivalente a calcular el permanente de una matriz 0-1.

Fig. 1. El número máximo de torres que no se atacan entre sí en un tablero de ajedrez de 8×8 es 8. Las torres más los puntos marcan las casillas de las columnas anuladas en las posiciones inferiores después de colocar las torres.

Un precursor del polinomio de las torres es el clásico "Problema de las ocho torres" ideado por H. E. Dudeney,^[3] en el que muestra que el número máximo de torres no atacantes en un tablero de ajedrez es ocho, colocándolas en una de las diagonales principales (Fig. 1). La pregunta es: "¿De cuántas maneras se pueden colocar ocho torres en un tablero de ajedrez de 8 × 8 para que ninguna de ellas ataque a la otra?" La respuesta es: "Obviamente debe haber una torre en cada fila y en cada columna. Comenzando con la fila de abajo, es claro que la primera torre puede ser puesta en cualquiera de las ocho casillas diferentes (Fig. 1). Dondequiera que se coloque, hay la opción de siete casillas para la segunda torre de la segunda fila. Luego, quedan seis cuadrados para seleccionar la tercera fila, cinco en la cuarta, y así sucesivamente. Por lo tanto, el número de formas diferentes debe ser 8 × 7 × 6 × 5 × 4 × 3 × 3 × 2 × 1 = 40.320 (es decir, 8!, donde "!" es factorial).^[4]

El mismo resultado puede obtenerse de una manera diferente. Dótese a cada torre de un número de posición, correspondiente al número de su fila, y asígnesele un nombre que corresponda al nombre de su fila. Así, la torre a1 tiene la posición 1 y el nombre "a", la torre b2 tiene la posición 2 y el nombre "b", etc. Entonces ordénense las torres en una lista ordenada (secuencia) por sus posiciones. El diagrama de la Fig. 1 se transformará en la secuencia (a,b,c,d,e,f,g,h). Colocar cualquier torre en otra casilla implicaría mover la torre que hasta ahora ocupaba el segundo fichero al fichero, desocupado por la primera torre. Por ejemplo, si la torre a1 se mueve a "b", la torre b2 debe ser movida a "a", y ahora se convertirán en la torre b1 y la torre a2. Por ejemplo, si la torre a1 se mueve a "b", la torre b2 debe ser movida a "a", y ahora se convertirán en la torre b1 y la torre a2. La nueva secuencia será (b,a,c,d,e,f,g,h). En combinatoria, esta operación se denomina permutación, y las secuencias, obtenidas como resultado de la permutación, se denominan las permutaciones de la secuencia dada. El número total de permutaciones, que contienen 8 elementos de una secuencia de 8 elementos es 8! (factorial de 8).

Para evaluar el efecto de la limitación impuesta "las torres no deben atacarse entre sí", considérese el problema sin dicha limitación. ¿De cuántas maneras se pueden colocar ocho torres en un tablero de ajedrez de 8 × 8? Este será el número total de combinaciones de 8 torres en 64 casillas:

${\displaystyle {64 \choose 8}={\frac {64!}{8!(64-8)!}}=4.426.165.368.}$

Por lo tanto, la limitación "las torres no deben atacarse entre sí" reduce el número total de posiciones permitidas de combinaciones a permutaciones, lo que es un factor de alrededor de 109.776.

Una serie de problemas de la actividad humana pueden reducirse al problema de la torre dándoles una "formulación de la torre". Por ejemplo: una empresa debe emplear a n trabajadores en n puestos de trabajo diferentes y cada puesto de trabajo debe ser realizado por un solo trabajador. ¿De cuántas maneras distintas se pueden organizar?

Pónganse los trabajadores en las filas del tablero de ajedrez y los trabajos en las columnas. Si el obrero i es designado para el trabajo j, se coloca una torre en la casilla donde la fila i cruza la fila j. Puesto que cada trabajo es llevado a cabo por un solo trabajador y cada trabajador es designado para un solo trabajo, todos los archivos y filas contendrán solo una torre como resultado de la disposición de las n torres en el tablero, es decir, las torres no se atacan entre sí.

El problema clásico de las torres da inmediatamente el valor de r₈, el coeficiente delante del término de orden más alto del polinomio de las torres. De hecho, su resultado es que 8 torres no atacantes pueden ser colocadas en un tablero de ajedrez de 8 × 8 en r₈ = 8! = 40320 maneras.

Se puede generalizar este problema considerando un tablero de m×n casillas, es decir, un tablero con m filas y n columnas. El problema es: ¿De cuántas maneras se pueden colocar k torres en un tablero de m×n casillas de tal manera que no se ataquen entre sí?

Está claro que para que el problema sea solucionable, k debe ser menor o igual al más pequeño de los números m y n; de lo contrario no se puede evitar colocar un par de torres en una misma fila. Una vez que se cumpla esta condición, a continuación, la disposición de las torres se puede llevar a cabo en dos pasos. En primer lugar, se debe elegir el conjunto de filas k para colocar las torres. Puesto que el número de filas es m, de los cuales deben elegirse k, esta elección puede hacerse de ${\displaystyle {\binom {m}{k}}}$ maneras. Del mismo modo, el conjunto de k columnas para colocar las torres se puede elegir de ${\displaystyle {\binom {n}{k}}}$ maneras. Dado que la elección de los ficheros no depende de la elección de las filas, según la regla de los productos hay ${\displaystyle {\binom {n}{k}}}$ formas de elegir la casilla en la que colocar la torre.

Sin embargo, la tarea aún no ha terminado, porque las k filas y las k columnas se cruzan en k² posiciones. Eliminando las filas y columnas no utilizados y compactando las filas y columnas restantes, se obtiene una nueva tabla de k filas y k columnas. Ya se ha demostrado que en dicho tablero las k torres pueden ser dispuestas de k maneras (para que no se ataquen entre sí). Por lo tanto, el número total de posibles configuraciones de torres no atacantes es:^[5]

${\displaystyle r_{k}={\binom {m}{k}}{\binom {n}{k}}k!={\frac {n!m!}{k!(n-k)!(m-k)!}}.}$

Por ejemplo, 3 torres pueden ser colocadas en un tablero de ajedrez convencional (8 × 8) en ${\displaystyle \textstyle {\frac {8!8!}{3!5!5!}}=18,816}$ maneras. Para k = m = n, la fórmula anterior da r_k = n! que corresponde al resultado obtenido para el problema de las torres clásicas.

El polinomio de la torre con coeficientes explícitos es ahora:

${\displaystyle R_{m,n}(x)=\sum _{k=0}^{\min(m,n)}{\binom {m}{k}}{\binom {n}{k}}k!x^{k}=\sum _{k=0}^{\min(m,n)}{\frac {n!m!}{k!(n-k)!(m-k)!}}x^{k}.}$

Si se elimina la limitación "las torres no deben atacarse entre sí", se debe elegir cualquier casilla k de las m×n casillas. Esto se puede hacer en:

${\displaystyle {\binom {mn}{k}}={\frac {(mn)!}{k!(mn-k)!}}}$ maneras.

Si las k torres difieren de alguna manera entre sí, por ejemplo, están etiquetadas o numeradas, todos los resultados obtenidos hasta ahora deben multiplicarse por k, el número de permutaciones de las k torres.

Como una complicación adicional al problema de las torres, se puede requerir que las torres no solo no se ataquen entre sí, sino que también estén dispuestas simétricamente en el tablero. Dependiendo del tipo de simetría, esto equivale a girar o reflejar el tablero.

Los arreglos simétricos conducen a muchos problemas, dependiendo de la condición de simetría.^[6][7][8][9]

Fig. 2. Una disposición simétrica de torres que no se atacan entre sí sobre el centro de un tablero de ajedrez de 8×8. Los puntos marcan los 4 cuadrados centrales que rodean el centro de simetría.

La más simple de esas disposiciones es cuando la posición de las torres es simétrica con respecto al centro del tablero. Desígnese con G_n el número de disposiciones en las que las n torres se colocan en un tablero con n filas y n columnas. Ahora, se hace que el tablero contenga 2n filas y 2n columnas. Una torre en la primera fila puede ser colocada en cualquiera de las 2n columnas de ese archivo. Según la condición de simetría, la colocación de esta torre define la colocación de la torre que se encuentra en la última fila, que debe ser colocada simétricamente a la primera torre respecto al centro del tablero. Se eliminan la primera y la última fila y las filas que están ocupadas por las torres (ya que el número de filas es par, las torres eliminadas no pueden estar en la misma fila). Esto dará un tablero de (2n-2) filas y de (2n-2) columnas. Está claro que a cada disposición simétrica de las torres en el nuevo tablero corresponde una disposición simétrica de las torres en el tablero original. Por lo tanto, G_2n = 2nG_2n − 2 (el factor 2n en esta expresión proviene de la posibilidad de que la primera torre ocupe cualquiera de las 2n casillas de la primera fila). Al iterar la fórmula anterior se llega al caso de una tabla de 2x2, en la que hay 2 disposiciones simétricas (en las diagonales). Como resultado de esta iteración, la expresión final es G_2n = 2ⁿn! Para el tablero de ajedrez habitual (de 8x8 casillas),G₈ = 2⁴ 4! = 16   24 = 384 disposiciones simétricas centrales de 8 torres. Una de estas disposiciones se muestra en la Fig. 2.

Para tablas de tamaño impar (que contienen (2n+1) filas y (2n+1) columnas) siempre hay un cuadrado que no tiene su doble simétrico - este es el cuadrado central del tablero. Siempre debe haber una torre colocada en esta casilla. Eliminando la fila y la columna centrales, se obtiene una disposición simétrica de 2n torres en un tablero de 2n x 2n. Por lo tanto, para dicho tablero, una vez más G_2n + 1 = G_2n = 2ⁿn!

Un problema un poco más complicado es encontrar el número de disposiciones sin ataque entre torres que no cambian con la rotación de 90° del tablero. Supóngase que el tablero tiene 4ncolumnas y 4n filas, y el número de torres es también 4n. En este caso, la torre que está en la primera fila puede ocupar cualquier casilla de este archivo, excepto las casillas de esquina (una torre no puede estar en una casilla de esquina porque después de una rotación de 90° habría 2 torres que se atacarían entre sí). Hay otras 3 torres que corresponden a esa torre y se encuentran, respectivamente, en la última columna, en la última fila y en la primera columna (se obtienen de la primera torre por rotaciones de 90°, 180° y 270°). Eliminando las filas y columnas de esas torres, se obtienen las disposiciones de las torres para un tablero de (4n − 4) × (4n − 4) con la simetría requerida. De este modo, se obtiene la siguiente relación de recurrencia: R_4n = (4n − 2)R_4n − 4, donde R_n es el número de disposiciones para un tablero de n × n casillas. Iterando, se deduce que R_4n = 2n(2n − 1)(2n − 3)...1. El número de posiciones para un tablero de (4n + 1) × (4n + 1) es el mismo que para una tabla de (4n × 4n); esto se debe a que en un tablero de (4n + 1) × (4n + 1), una torre debe necesariamente estar en el centro y por lo tanto la fila y la columna centrales pueden eliminarse. Por lo tanto, R_4n + 1 = R_4n. Para el tablero de ajedrez tradicional (n = 2), existen 4 × 3 × 1 = 12 disposiciones posibles con simetría rotacional.

Para tableros de (4n + 2) × (4n + 2) and (4n + 3) × (4n + 3) casillas, el número de soluciones es cero. Dos casos son posibles para cada torre: o está en el centro o no está en el centro. En el segundo caso, esta torre está incluida en el cuarteto de torres que intercambian casillas al girar el tablero a 90°. Por lo tanto, el número total de torres debe ser de 4n (cuando no hay un cuadrado central en el tablero) o 4n + 1. Esto prueba que R_4n + 2 = R_4n + 3 = 0.

El número de disposiciones simétricas de n torres no atacantes en una de las diagonales (para su determinación, la diagonal correspondiente a a1-h8 en el tablero de ajedrez) en un tablero de n × n casillas, está definido por la recurrencia Q_n = Q_n 1 + (n- - 1)Q_n- - 2. Esta recurrencia se deriva de la siguiente manera. Obsérvese que la torre en la primera fila está en la casilla de la esquina inferior o está en otra casilla. En el primer caso, la eliminación de la primera fila y de la primera columna conduce a la disposición simétrica de n-1 torres en una tabla de (n-1×n-1). El número de tales disposiciones es Q_n − 1. En el segundo caso, para la torre original hay otra, simétrica a la primera sobre la diagonal elegida. La eliminación de las filas y columnas de esas torres conduce a una disposición simétrica de n-2 torres en un tablero de (n − 2) × (n − 2) casillas. Puesto que el número de tales posiciones es Q_n − 2 y la torre puede colocarse en la n − 1 casilla de la primera fila, hay (n − 1)Q_n − 2 formas de hacer esto, lo que permite deducir una fórmula recurrente. El número de disposiciones diagonales simétricas viene dado por la expresión:

${\displaystyle Q_{n}=1+{\binom {n}{2}}+{\frac {1}{1\times 2}}{\binom {n}{2}}{\binom {n-2}{2}}+{\frac {1}{1\times 2\times 3}}{\binom {n}{2}}{\binom {n-2}{2}}{\binom {n-4}{2}}+\cdots .}$

Esta expresión se deriva de la partición de todos las disposiciones de torres en clases; en la clase s están aquellas posiciones en las que los pares de torres s no se encuentran en la diagonal. Exactamente de la misma manera, se puede demostrar que el número de las disposiciones de 'n-torres en un tablero de n × n casillas, de tal manera que no se atacan entre sí y son simétricas a ambas diagonales, viene dado por las ecuaciones de recurrencia B₂n = 2B₂n − 2 + (2n − 2)B₂n − 4 and B₂n + 1 = B₂n.

Un tipo diferente de generalización es aquella en la que las disposiciones de torres que se obtienen por simetrías del tablero se cuentan como una sola. Por ejemplo, si se permite girar el tablero 90 grados como simetría, entonces cualquier arreglo obtenido por una rotación de 90, 180 o 270 grados se considera "el mismo" que el patrón original, aunque estos arreglos se cuentan por separado en el problema original donde el tablero está fijo. Para tales problemas, Dudeney^[10] observa que:

Todavía no se ha determinado cuántas maneras hay si las meras inversiones y reflexiones no se cuentan como diferentes; es un problema difícil.

El problema se reduce al de contar arreglos simétricos mediante el lema de Burnside.