En las matemáticas relacionadas con la combinatoria, un polinomio de torre, es una expresión numérica que genera el número de formas de colocar una serie de torres que no se atacan entre sí en un tablero similar a uno de ajedrez, aunque de dimensión variable. No existe la posibilidad de que dos torres se encuentren en la misma fila o columna. El tablero es cualquier subconjunto de las casillas de un tablero rectangular con m filas y n columnas. Coincide con el tablero de ajedrez común si cualquier casilla puede ser ocupada por una pieza y m=n=8, y m=n.
El coeficiente de xk en el polinomio torre RB(x), es el número de maneras en que las k torres (ninguna de las cuales ataca a otra), pueden ser dispuestas en los cuadrados del tablero B. Las torres están dispuestas de tal manera que no hay dos torres en la misma fila o columna. En este sentido, una forma de colocarlas es situar las torres en una tabla estática e inmóvil. La configuración no será diferente mientras se mantengan las casillas fijas. El polinomio también permanece igual, aunque se cambien filas por columnas.
Historia El término polinomio de torre fue acuñado por el matemático John Riordan.John Riordan, An Introduction to Combinatorial Analysis, Princeton University Press, 1980 (originally published by John Wiley and Sons, New York; Chapman and Hall, London, 1958) ISBN 978-0-691-02365-6 (reprinted again in 2002, by Dover Publications). Véanse capítulos 7 & 8. A pesar de que la denominación procede del mundo del ajedrez, el interés por 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 de nxn casilas, corresponde a las permutaciones de n objetos, que pueden tomarse como los números 1,2,...,n, de tal manera que el número aj 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. Los ejemplos más famosos incluyen numerosas formas de colocar torres de forma que no se ataquen entre sí: En un tablero de ajedrez completo de n×n casillas, que es un problema combinatorio elemental; En el mismo tablero pero con sus cuadrados diagonales prohibidos; este es el problema del "hat-check"; En el mismo tablero pero sin los cuadrados en su diagonal e inmediatamente por encima de su diagonal (y sin el cuadrado inferior izquierdo), que es esencial en la solución del problème des ménages. El interés por las disposiciones de torres surge a partir de 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 función de generación, y también del hecho de que los ceros del polinomio de torre de un tablero proporcionan información valiosa sobre sus coeficientes, es decir, sobre el número de ubicaciones de k torres que no se atacan entre sí.
Definición El polinomio de torre RB(x) de un tablero B es la función generadora para el número de disposiciones de torres no atacantes entre sí:
donde rk es el número de maneras de colocar k torres que no se atacan entre sí en el tablero. A pesar de la notación, esta es una suma finita, ya que el tablero es finito, por lo que hay un número máximo de torres no atacantes que se pueden colocar en cada caso; de hecho, no puede haber más torres que el menor del número de filas y de columnas en el tablero.
Tableros completos Los primeros polinomios de torre en tableros cuadrados de n × n casillas (Rn = RB) son:
En otras palabras, esto significa que en un tablero de 1 × 1, una torre puede ser colocada de una sola manera, y las cero torres también pueden ser colocadas de un única manera (tablero vacío); en un tablero completo de 2 × 2, dos torres pueden ser colocadas de dos maneras (en las diagonales), una torre puede ser colocada de cuatro maneras, y las cero torres pueden ser colocadas de una única manera; y así sucesivamente para tableros más grandes.
Para tableros rectangulares Bm,n de m × n casillas, se escribe Rm,n := RBm,n . El menor de m y n puede tomarse como el límite superior para k, ya que obviamente rk = 0 si k > min(m, n).
Esto también se comprueba en la fórmula para Rm,n(x). El polinomio de torre de un tablero de ajedrez rectangular está estrechamente relacionado con el polinomio generalizado de Laguerre Lnα(x) por la identidad.
Polinomios coincidentes
Un polinomio de torre es un caso especial de un tipo de polinomio coincidente, que es la función generadora del número de k-borde en un gráfico.
El polinomio de la torre Rm,n(x) corresponde al gráfico bipartito completo Km,n . El polinomio de torre de un tablero general B ⊆ Bm,n corresponde al gráfico bipartito con vértices a la izquierda v1, v2, ..., vm y vértices de la derecha w1, w2, ..., wn y un borde viwj siempre que la casilla (i, j) esté permitida, es decir, pertenece aB. Así, la teoría de los polinomios de torre está, en cierto sentido, contenida en la de los polinomios coincidentes.
Se deduce un hecho importante sobre los coeficientes rk, dado el número de colocaciones no atacantes de las k torres en B: estos números son unimodales, es decir, aumentan al máximo y luego disminuyen. Esto se desprende (mediante un argumento estándar) del teorema de Heilmann y LiebOle J. Heilmann and Elliott H. Lieb, Theory of monomer-dimer systems. "Comunicaciones en Física Matemática", Vol. 25 (1972), págs. 190-232. 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), lo que implica que todos los ceros de un polinomio de torre son números reales negativos.
Conexión con el permanente de una matriz
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.
Tableros rectangulares completos
Problema de las torres
Un precursor del polinomio de las torres es el clásico "Problema de las ocho torres" ideado por H. E. Dudeney,Dudeney, Henry E. Amusements In Mathematics. 1917. Nelson. (reeditado por Plain Label Books: También como una colección de recortes de periódicos, Dover Publications, 1958; Kessinger Publishing, 2006). El libro puede ser descargado gratuitamente desde el sitio Proyecto Gutenberg 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).Dudeney, Problema 295
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:
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 polinomio de torre como una generalización del problema de las torres El problema clásico de las torres da inmediatamente el valor de r8, 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 r8 = 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 maneras. Del mismo modo, el conjunto de k columnas para colocar las torres se puede elegir de 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 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 k2 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:Vilenkin, Naum Ya. Combinatoria (Kombinatorika). 1969. Nauka Publishers, Moscú (Rusia).