En matemáticas combinatorias , un polinomio de torre es un polinomio generador del número de formas de colocar torres no atacantes en un tablero que parece un tablero de ajedrez ; es decir, no pueden haber dos torres en la misma fila o columna. El tablero es cualquier subconjunto de los cuadrados de un tablero rectangular con m filas y n columnas; lo pensamos como los cuadrados en los que se permite poner una torre. El tablero es el tablero de ajedrez ordinario si se permiten todos los cuadrados y m = n = 8 y un tablero de ajedrez de cualquier tamaño si se permiten todos los cuadrados y m = n . El coeficiente de x k en el polinomio de torre R B ( x ) es el número de formas en que k torres, ninguna de las cuales ataca a otra, pueden organizarse en los cuadrados de B . Las torres se organizan de tal manera que no hay un par de torres en la misma fila o columna. En este sentido, una disposición es el posicionamiento de las torres en un tablero estático e inamovible; La disposición no será diferente si se gira o refleja el tablero manteniendo las casillas estacionarias. El polinomio también permanece igual si se intercambian las filas o las columnas.
El término "polinomio de torre" fue acuñado por John Riordan . [1] A pesar de que el nombre deriva del ajedrez , el impulso para estudiar los polinomios de torre es su conexión con el conteo de permutaciones (o permutaciones parciales ) con posiciones restringidas. Un tablero B que es un subconjunto del tablero de ajedrez n × n corresponde a permutaciones de n objetos, que podemos tomar como los números 1, 2, ..., n , de modo que el número a j en la posición j -ésima en la permutación debe ser el número de columna de un cuadrado permitido en la fila j de B . Ejemplos famosos incluyen la cantidad de formas de colocar n torres no atacantes en:
El interés por la colocación de las torres surge en la combinatoria pura y aplicada, la teoría de grupos , la teoría de números y la física estadística . El valor particular de los polinomios de torre proviene de la utilidad del enfoque de la función generadora, y también del hecho de que los ceros del polinomio de torre de un tablero brindan información valiosa sobre sus coeficientes, es decir, el número de colocaciones no atacantes de k torres.
El polinomio de torre R B ( x ) de un tablero B es la función generadora de los números de disposiciones de torres no atacantes:
donde es el número de formas de colocar k torres no atacantes en el tablero B. Hay un número máximo de torres no atacantes que el tablero puede contener; de hecho, no puede haber más torres que el número de filas o el número de columnas en el tablero (de ahí el límite ). [2]
Para tableros rectangulares m × n B m , n , escribimos R m,n := R B m , n , y si m = n , R n := R m , n .
Los primeros polinomios de torre en tableros cuadrados de n × n son:
En palabras, esto significa que en un tablero de 1 × 1, 1 torre se puede organizar de 1 manera, y cero torres también se pueden organizar de 1 manera (tablero vacío); en un tablero completo de 2 × 2, 2 torres se pueden organizar de 2 maneras (en las diagonales), 1 torre se puede organizar de 4 maneras, y cero torres se pueden organizar de 1 manera; y así sucesivamente para tableros más grandes.
El polinomio de la torre de un tablero de ajedrez rectangular está estrechamente relacionado con el polinomio de Laguerre generalizado L n α ( x ) por la identidad
Un polinomio de torre es un caso especial de un tipo de polinomio coincidente , que es la función generadora del número de coincidencias de k aristas en un gráfico.
El polinomio de torre R m , n ( x ) corresponde al grafo bipartito completo K m , n . El polinomio de torre de un tablero general B ⊆ B m , n corresponde al grafo bipartito con vértices izquierdos v 1 , v 2 , ..., v m y vértices derechos w 1 , w 2 , ..., w n y una arista v i w j siempre que se permita la casilla ( i , j ), es decir, pertenezca a B . Así pues, la teoría de los polinomios de torre está, en cierto sentido, contenida en la de los polinomios coincidentes.
Deducimos un hecho importante sobre los coeficientes r k , que recordamos dado el número de colocaciones no atacantes de k torres en B : estos números son unimodales , es decir, aumentan hasta un máximo y luego disminuyen. Esto se sigue (por un argumento estándar) del teorema de Heilmann y Lieb [3] sobre los ceros de un polinomio coincidente (uno diferente del que corresponde a un polinomio de torre, pero equivalente a él bajo un cambio de variables), que implica que todos los ceros de un polinomio de torre son números reales negativos.
Para tableros de cuadrados incompletos n × n (es decir, no se permite jugar torres en un subconjunto arbitrario de los cuadrados del tablero), calcular el número de formas de colocar n torres en el tablero es equivalente a calcular el permanente de una matriz 0-1.
Un precursor del polinomio de la torre es el clásico "Problema de las ocho torres" de HE Dudeney [4], en el que demuestra 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 que se plantea es: "¿De cuántas maneras se pueden colocar ocho torres en un tablero de ajedrez de 8 × 8 de modo que ninguna de ellas ataque a la otra?" La respuesta es: “Obviamente debe haber una torre en cada fila y en cada columna. Empezando por la fila inferior, está claro que la primera torre puede colocarse en cualquiera de ocho casillas diferentes (Fig. 1). Dondequiera que se coloque, existe la opción de siete casillas para la segunda torre en la segunda fila. Luego hay seis casillas de las que 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 × 2 × 1 = 40.320” (es decir, 8!, donde “!” es el factorial ). [5]
El mismo resultado puede obtenerse de una manera ligeramente diferente. Dotemos a cada torre de un número de posición, correspondiente al número de su rango, y asignemosle un nombre que corresponda al nombre de su columna. 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. Ordenemos entonces las torres en una lista ordenada ( secuencia ) por sus posiciones. El diagrama de la Fig. 1 se transformará entonces en la secuencia (a,b,c,d,e,f,g,h). Colocar cualquier torre en otra columna implicaría mover la torre que hasta entonces ocupaba la segunda columna a la columna que dejó libre la primera torre. Por ejemplo, si la torre a1 se mueve a la columna "b", la torre b2 debe moverse a la columna "a", y ahora se convertirán en torre b1 y torre a2. La nueva secuencia se convertirá en (b,a,c,d,e,f,g,h). En combinatoria, esta operación se denomina permutación y las sucesiones obtenidas como resultado de la permutación son permutaciones de la sucesión dada. El número total de permutaciones que contienen 8 elementos de una sucesión de 8 elementos es 8! ( factorial de 8).
Para evaluar el efecto de la limitación impuesta "las torres no deben atacarse entre sí", consideremos 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:
De esta forma, la limitación "las torres no deben atacarse entre sí" reduce el número total de posiciones permitidas desde combinaciones hasta permutaciones, que es un factor de aproximadamente 109.776.
Se pueden reducir al problema de la torre una serie de problemas de diferentes esferas de la actividad humana, dándoles una "formulación de la torre". A modo de ejemplo: una empresa debe emplear a n trabajadores en n trabajos diferentes y cada trabajo debe ser realizado por un solo trabajador. ¿De cuántas maneras se puede realizar esta designación?
Coloquemos a los trabajadores en las filas del tablero de ajedrez de n × n y los trabajos − en las columnas. Si al trabajador i se le asigna la tarea j , se coloca una torre en la casilla donde la fila i cruza la columna j . Como cada tarea la realiza un solo trabajador y cada trabajador está asignado a una sola tarea, todas las columnas y filas contendrán solo una torre como resultado de la disposición de n torres en el tablero, es decir, las torres no se atacan entre sí.
El problema clásico de las torres proporciona inmediatamente el valor de r 8 , el coeficiente que se encuentra delante del término de orden más alto del polinomio de torres. De hecho, su resultado es que se pueden disponer 8 torres no atacantes en un tablero de ajedrez de 8 × 8 de r 8 = 8! = 40320 formas.
Generalicemos este problema considerando un tablero de m × n , es decir, un tablero con m filas (filas) y n columnas (columnas). El problema se convierte en: ¿De cuántas maneras se pueden disponer k torres en un tablero de m × n de tal manera que no se ataquen entre sí?
Es claro que para que el problema sea solucionable, k debe ser menor o igual al menor de los números m y n ; de lo contrario, no se puede evitar colocar un par de torres en una fila o en una columna. Sea que esta condición se cumpla. Entonces, la disposición de las torres se puede llevar a cabo en dos pasos. Primero, elegir el conjunto de k filas en las que colocar las torres. Como el número de filas es m , de las cuales k deben elegirse, esta elección se puede hacer de maneras. De manera similar, el conjunto de k columnas en las que colocar las torres se puede elegir de maneras. Como la elección de las columnas no depende de la elección de las filas, de acuerdo con la regla de los productos hay maneras de elegir la casilla en la que colocar la torre.
Sin embargo, la tarea aún no ha terminado porque k filas y k columnas se intersecan en k 2 casillas. Al eliminar filas y columnas no utilizadas y compactar las filas y columnas restantes, se obtiene un nuevo tablero de k filas y k columnas. Ya se ha demostrado que en dicho tablero se pueden disponer k torres de k ! maneras (de modo que no se ataquen entre sí). Por lo tanto, el número total de posibles disposiciones de torres no atacantes es: [6]
Por ejemplo, en un tablero de ajedrez convencional (8 × 8) se pueden colocar 3 torres de distintas maneras. Para k = m = n , la fórmula anterior da r k = n ! que corresponde al resultado obtenido para el problema clásico de las torres.
El polinomio de torre con coeficientes explícitos ahora es:
Si se elimina la limitación de que las torres no deben atacarse entre sí, se deben elegir k casillas cualesquiera de entre m × n casillas. Esto se puede hacer de la siguiente manera:
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 k torres.
Como complicación adicional del problema de las torres, supongamos que las torres no sólo no atacan, sino que además están dispuestas simétricamente en el tablero. Según el tipo de simetría, esto equivale a rotar o reflejar el tablero. Las disposiciones simétricas conducen a muchos problemas, según la condición de simetría. [7] [8] [9] [10]
La disposición más simple es aquella en la que las torres son simétricas respecto del centro del tablero. Designemos con G n el número de disposiciones en las que se colocan n torres en un tablero con n filas y n columnas. Ahora hagamos que el tablero contenga 2 n filas y 2 n columnas. Una torre en la primera fila puede colocarse en cualquiera de las 2 n casillas de esa columna. De acuerdo con 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 columna: debe estar dispuesta simétricamente con respecto a la primera torre respecto del centro del tablero. Quitemos la primera y la última columna y las filas que están ocupadas por 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 2 n − 2 columnas y 2 n − 2 filas. Es evidente que a cada disposición simétrica de torres en el nuevo tablero corresponde una disposición simétrica de torres en el tablero original. Por tanto, G 2 n = 2 nG 2 n − 2 (el factor 2 n en esta expresión proviene de la posibilidad de que la primera torre ocupe cualquiera de las 2 n casillas de la primera fila). Iterando la fórmula anterior se llega al caso de un tablero de 2 × 2, en el que hay 2 disposiciones simétricas (en las diagonales). Como resultado de esta iteración, la expresión final es G 2 n = 2 n n ! Para el tablero de ajedrez habitual (8 × 8), G 8 = 2 4 × 4! = 16 × 24 = 384 disposiciones simétricas centrales de 8 torres. Una de estas disposiciones se muestra en la figura 2.
En los tableros de tamaño impar (que contienen 2 n + 1 filas y 2 n + 1 columnas), siempre hay una casilla que no tiene su doble simétrico: esta es la casilla central del tablero. Siempre debe haber una torre colocada en esta casilla. Quitando la columna y la fila centrales, se obtiene una disposición simétrica de 2 n torres en un tablero de 2 n × 2 n . Por lo tanto, para dicho tablero, una vez más G 2 n + 1 = G 2 n = 2 n n !.
Un problema un poco más complicado es encontrar el número de disposiciones no atacantes que no cambian al rotar el tablero 90°. Sea el tablero de 4 n columnas y 4 n filas, y el número de torres también es 4 n . En este caso, la torre que está en la primera columna puede ocupar cualquier casilla de esta columna, excepto las casillas de las esquinas (una torre no puede estar en una casilla de las esquinas 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 fila, la última columna y la primera fila (se obtienen a partir de la primera torre mediante rotaciones de 90°, 180° y 270°). Quitando las columnas y filas de esas torres, se obtienen las disposiciones de torres para un tablero de (4 n − 4) × (4 n − 4) con la simetría requerida. De esta forma, se obtiene la siguiente relación de recurrencia : R 4 n = (4 n − 2) R 4 n − 4 , donde R n es el número de disposiciones para un tablero de n × n . Iterando, se deduce que R 4 n = 2 n (2 n − 1)(2 n − 3)...1. El número de disposiciones para un tablero de (4 n + 1) × (4 n + 1) es el mismo que para un tablero de 4 n × 4 n ; esto se debe a que en un tablero de (4 n + 1) × (4 n + 1), una torre debe estar necesariamente en el centro y, por lo tanto, la fila y la columna centrales pueden eliminarse. Por lo tanto, R 4 n + 1 = R 4 n . Para el tablero de ajedrez tradicional ( n = 2), R 8 = 4 × 3 × 1 = 12 posibles disposiciones con simetría rotacional.
Para los tableros (4 n + 2) × (4 n + 2) y (4 n + 3) × (4 n + 3) el número de soluciones es cero. Para cada torre hay dos casos posibles: o bien está en el centro o bien 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 90°. Por lo tanto, el número total de torres debe ser o bien 4 n (cuando no hay casilla central en el tablero) o bien 4 n + 1. Esto demuestra que R 4 n + 2 = R 4 n + 3 = 0.
El número de disposiciones de n torres no atacantes simétricas a una de las diagonales (para la determinación, la diagonal correspondiente a a1–h8 en el tablero de ajedrez) en un tablero n × n está dado por los números de teléfono definidos por la recurrencia Q n = Q n − 1 + ( n − 1) Q n − 2 . Esta recurrencia se deriva de la siguiente manera. Nótese que la torre en la primera columna se encuentra en la casilla de la esquina inferior o en otra casilla. En el primer caso, la eliminación de la primera columna y la primera fila conduce a la disposición simétrica n − 1 torres en un tablero ( n − 1) × ( n − 1) . El número de tales disposiciones es Q n − 1 . En el segundo caso, para la torre original hay otra torre, simétrica a la primera respecto a la diagonal elegida. La eliminación de las columnas y filas de esas torres conduce a una disposición simétrica de n − 2 torres en un tablero ( n − 2) × ( n − 2). Dado que el número de tales disposiciones es Q n − 2 y la torre se puede colocar en la casilla n − 1 de la primera columna, hay ( n − 1) Q n − 2 formas de hacerlo, lo que inmediatamente da la recurrencia anterior. El número de disposiciones diagonalmente simétricas viene dado por la expresión:
Esta expresión se deriva de la partición de todas las disposiciones de torres en clases; en la clase s están aquellas disposiciones en las que s pares de torres no se encuentran en la diagonal. Exactamente de la misma manera, se puede demostrar que el número de disposiciones de n torres en un tablero n × n , tales que no se ataquen entre sí y sean simétricas a ambas diagonales, está dado por las ecuaciones de recurrencia B 2 n = 2 B 2 n − 2 + (2 n − 2) B 2 n − 4 y B 2 n + 1 = B 2 n .
Un tipo diferente de generalización es aquella en la que las disposiciones de torres que se obtienen entre sí por simetrías del tablero se cuentan como una sola. Por ejemplo, si se permite rotar el tablero 90 grados como simetría, entonces cualquier disposición obtenida por una rotación de 90, 180 o 270 grados se considera "la misma" que el patrón original, aunque estas disposiciones se cuenten por separado en el problema original donde el tablero está fijo. Para tales problemas, Dudeney [11] observa: "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 disposiciones simétricas mediante el lema de Burnside .
