En matemática combinatoria , un polinomio de torre es un polinomio generador de la cantidad de formas de colocar torres que no atacan en un tablero que parece un tablero de ajedrez ; es decir, no puede haber dos torres en la misma fila o columna. El tablero es cualquier subconjunto de los cuadrados de un tablero rectangular con m filas yn columnas; lo pensamos como las casillas en las 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 la torre polinomio R B ( x ) es el número de formas k torres, ninguno de los cuales los ataques de otros, pueden estar dispuestos en los cuadrados de B . Las torres están dispuestas de tal manera que no haya un par de torres en la misma fila o columna. En este sentido, un arreglo es el posicionamiento de torres sobre un tablero estático e inamovible; la disposición no será diferente si el tablero se gira o se refleja mientras se mantienen los cuadrados estacionarios. El polinomio también permanece igual si se intercambian filas o columnas.
El término "polinomio de torre" fue acuñado por John Riordan . [1] A pesar de la derivación del nombre del ajedrez , el ímpetu para estudiar polinomios de torres 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 j -ésima posición en la permutación debe ser el número de columna de un cuadrado permitido en la fila j de B . Los ejemplos famosos incluyen la cantidad de formas de colocar n torres no atacantes en:
- un tablero de ajedrez completo de n × n , que es un problema combinatorio elemental;
- el mismo tablero con sus cuadrados diagonales prohibidos; este es el problema del trastorno o "chequeo de sombrero" (este es un caso particular del problema de los rencontres );
- el mismo tablero sin los cuadrados en su diagonal e inmediatamente encima de su diagonal (y sin el cuadrado inferior izquierdo), que es esencial en la solución del problema de los ménages .
El interés en la colocación de 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 proporcionan información valiosa sobre sus coeficientes, es decir, el número de ubicaciones de k torres sin atacar. .
Definición
El polinomio de torres R B ( x ) de un tablero B es la función generadora del número de arreglos de torres que no atacan:
donde r k es el número de formas de colocar k torres no atacantes en un tablero de m filas yn columnas. Hay un número máximo de torres no atacantes que el tablero puede contener; de hecho, no puede haber más torres que la menor de las filas y columnas del tablero (de ahí el límite). [2]
Tablas completas
Los primeros polinomios de torres en tableros cuadrados n × n son (con R n = R B ):
En palabras, esto significa que en un tablero 1 × 1, se puede disponer 1 torre de 1 manera, y también se pueden ordenar cero torres de 1 manera (tablero vacío); en un tablero completo de 2 × 2, se pueden colocar 2 torres de 2 maneras (en las diagonales), 1 torre se puede ordenar de 4 maneras y cero torres se pueden ordenar de 1 manera; y así sucesivamente para tablas más grandes.
Para m × n tableros rectangulares completos B m , n escribimos R m, n : = R B m , n . El más pequeño de m y n puede tomarse como un límite superior para k , ya que obviamente r k = 0 si k > min ( m , n ). Esto también se muestra en la fórmula para R m, n ( x ).
El polinomio de torre de un tablero de ajedrez rectangular está estrechamente relacionado con el polinomio de Laguerre generalizado L n α ( 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 coincidencias de k -edge en un gráfico.
El polinomio de la torre R m , n ( x ) corresponde al gráfico bipartito completo K m , n . El polinomio de la torre de un tablero general B ⊆ B m , n corresponde al gráfico bipartito con vértices izquierdos v 1 , v 2 , ..., v m y vértices derechos w 1 , w 2 , ..., w n y an borde v i w j cada vez (el cuadrado i , j ) es permitido, es decir, pertenece a B . Por tanto, la teoría de los polinomios de torre está, en cierto sentido, contenida en la de los polinomios coincidentes.
Deducimos un dato 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 al 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.
Conexión a los permanentes de la matriz
Para n × n tableros cuadrados incompletos (es decir, no se permite jugar torres en algún 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 .
Tableros rectangulares completos
Problemas de torres
a | B | C | D | mi | F | gramo | h | ||
8 | 8 | ||||||||
7 | 7 | ||||||||
6 | 6 | ||||||||
5 | 5 | ||||||||
4 | 4 | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
a | B | C | D | mi | F | gramo | h |
Un precursor del polinomio de torres es el clásico "Problema de las ocho torres" de HE Dudeney [4] en el que muestra que el número máximo de torres que no atacan en un tablero de ajedrez es ocho colocándolas en una de las diagonales principales (Fig. 1). La pregunta que se hace es: "¿De cuántas formas 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 inferior, está claro que la primera torre se puede colocar en cualquiera de las ocho casillas diferentes (Fig. 1). Donde sea que esté colocado, existe la opción de siete casillas para la segunda torre en la segunda fila. Luego hay seis casillas para seleccionar la tercera fila, cinco en la cuarta, y así sucesivamente. Por lo tanto, el número de caminos diferentes debe ser 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40,320 "(es decir, 8 !, donde"! "Es factorial ). [5]
El mismo resultado se puede obtener de una manera ligeramente diferente. Dotemos a cada torre con un número posicional, correspondiente al número de su rango, y asignemos un nombre que corresponda al nombre de su archivo. 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 ordenemos 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 fila implicaría mover la torre que hasta ese momento ocupaba la segunda fila a la fila, dejada vacante por 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 secuencias, obtenidas como resultado de la permutación, son permutaciones de la secuencia dada. ¡El número total de permutaciones, que contiene 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í", considere el problema sin esa limitación. ¿De cuántas formas 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, que es un factor de aproximadamente 109,776.
Varios problemas de diferentes esferas de la actividad humana pueden reducirse al problema de la torre dándoles una "formulación de torre". A modo de ejemplo: una empresa debe emplear n trabajadores en n trabajos diferentes y cada trabajo debe ser realizado por un solo trabajador. ¿De cuántas formas se puede realizar esta cita?
Pongamos a los trabajadores en las filas del tablero de ajedrez n × n , y los trabajos, en los archivos. Si el trabajador i es designado para el trabajo j , se coloca una torre en el cuadrado donde el rango i cruza la fila j . Dado que cada trabajo es realizado por un solo trabajador y cada trabajador es designado para un solo trabajo, todos los archivos y rangos contendrán solo una torre como resultado de la disposición de n torres en el tablero, es decir, las torres no atacan El uno al otro.
El polinomio de torres como generalización del problema de torres
El problema clásico de torres da inmediatamente el valor de r 8 , el coeficiente frente al término de mayor orden del polinomio de torres. De hecho, ¡su resultado es que se pueden colocar 8 torres no atacantes en un tablero de ajedrez de 8 × 8 en r 8 = 8! = 40320 vías.
Generalicemos este problema considerando un tablero m × n , es decir, un tablero con m rangos (filas) y n archivos (columnas). El problema es: ¿De cuántas formas se pueden colocar k torres en un tablero m × n de tal manera que no se ataquen entre sí?
Es evidente que para que el problema sea resoluble, k debe ser menor o igual que el 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 fila o en una fila. Que se cumpla esta condición. Luego, la disposición de las torres se puede realizar en dos pasos. Primero, elija el conjunto de k rangos en los que colocar las torres. Dado que el número de rangos es m , de los cuales se debe elegir k , esta elección se puede hacer enformas. Del mismo modo, el conjunto de archivos k en los que colocar las torres se puede elegir enformas. Debido a que la elección de archivos no depende de la elección de rangos, de acuerdo con la regla de productos hay formas de elegir la casilla en la que colocar la torre.
Sin embargo, la tarea aún no está terminada porque k rangos y k archivos se cruzan en k 2 cuadrados. Eliminando rangos y archivos no utilizados y compactando los rangos y archivos restantes juntos, se obtiene un nuevo tablero de k rangos yk archivos. ¡Ya se demostró que en tal tablero se pueden ordenar k torres en k ! formas (para que no se ataquen entre sí). Por lo tanto, el número total de posibles arreglos de torres no atacantes es: [6]
Por ejemplo, se pueden colocar 3 torres en un tablero de ajedrez convencional (8 × 8) en formas. 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 ahora es:
Si se elimina la limitación "las torres no deben atacarse entre sí", se debe elegir cualquier k casillas de m × n casillas. Esto se puede hacer en:
- formas.
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.
Arreglos simétricos
Como complicación adicional del problema de las torres, exijamos que las torres no solo sean no atacantes sino que también estén dispuestas simétricamente en el tablero. Dependiendo del tipo de simetría, esto equivale a rotar o reflejar el tablero. Los arreglos simétricos dan lugar a muchos problemas, dependiendo de la condición de simetría. [7] [8] [9] [10]
a | B | C | D | mi | F | gramo | h | ||
8 | 8 | ||||||||
7 | 7 | ||||||||
6 | 6 | ||||||||
5 | 5 | ||||||||
4 | 4 | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
a | B | C | D | mi | F | gramo | h |
El más simple de esos arreglos es cuando las torres son simétricas con respecto al centro del tablero. Designemos con G n el número de arreglos en los que se colocan n torres en un tablero con n filas y n archivos. Ahora hagamos que el tablero contenga 2 n rangos y 2 n archivos. Se puede colocar una torre en la primera columna en cualquiera de los 2 n cuadrados de esa columna. De acuerdo con la condición de simetría, la ubicación de esta torre define la ubicación de la torre que se encuentra en la última fila; debe estar dispuesta simétricamente a la primera torre alrededor del centro del tablero. Eliminemos el primer y último archivo y los rangos que están ocupados por torres (dado que el número de rangos es par, las torres eliminadas no pueden estar en el mismo rango). Esto le dará un tablero de 2 n - 2 archivos y 2 n - 2 rangos. Está claro 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 lo 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 los 2 n cuadrados de la primera fila). Al iterar 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 arreglos centralmente simétricos de 8 torres. Una de estas disposiciones se muestra en la Fig.2.
Para tableros de tamaño impar (que contienen 2 n + 1 rangos y 2 n + 1 archivos) 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 lima central y el rango, se obtiene una disposición simétrica de 2 n torres en un tablero de 2 n × 2 n . Por lo tanto, para tal 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 arreglos no atacantes que no cambian con la rotación de 90 ° de la tabla. Supongamos que el tablero tiene 4 n archivos y 4 n rangos, y el número de torres también es 4 n . En este caso, la torre que está en la primera fila puede ocupar cualquier casilla de esta fila, 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 atacan entre sí). Hay otras 3 torres que corresponden a esa torre y se ubican, respectivamente, en la última fila, la última fila y la primera fila (se obtienen de la primera torre en rotaciones de 90 °, 180 ° y 270 °). Eliminando las filas y filas de esas torres, se obtienen los arreglos de torres para un tablero (4 n - 4) × (4 n - 4) con la simetría requerida. Así, 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 arreglos para un tablero n × n . Iterando, se sigue que R 4 n = 2 n (2 n - 1) (2 n - 3) ... 1. El número de arreglos para una placa (4 n + 1) × (4 n + 1) es el mismo que para una placa de 4 n × 4 n ; esto se debe a que en un tablero (4 n + 1) × (4 n + 1), una torre debe estar necesariamente en el centro y, por lo tanto, la fila y la fila 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 arreglos posibles con simetría rotacional.
Para tablas (4 n + 2) × (4 n + 2) y (4 n + 3) × (4 n + 3), el número de soluciones es cero. Son posibles dos casos para cada torre: o está en el centro o no está en el centro. En el segundo caso, esta torre se incluye en el cuarteto de torres que intercambia casillas al girar el tablero a 90 °. Por lo tanto, el número total de torres debe ser 4 n (cuando no hay un cuadrado central en el tablero) o 4 n + 1. Esto prueba que R 4 n + 2 = R 4 n + 3 = 0.
El número de arreglos 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 de n × n viene dada por los números de teléfono definidos por la recurrencia Q n = Q norte - 1 + ( norte - 1) Q norte - 2 . Esta recurrencia se deriva de la siguiente manera. Tenga en cuenta que la torre de la primera fila se encuentra en el cuadrado de la esquina inferior o en otro cuadrado. En el primer caso, la eliminación de la primera fila y la primera fila conduce a la disposición simétrica de n - 1 torres en un tablero ( n - 1) × ( n - 1). El número de tales arreglos es Q n - 1 . En el segundo caso, para la torre original hay otra torre, simétrica a la primera sobre la diagonal elegida. La eliminación de las filas y rangos 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 arreglos es Q n - 2 y la torre se puede colocar en el n - 1 cuadrado de la primera fila, hay ( n - 1) Q n - 2 formas de hacerlo, lo que da inmediatamente la recurrencia anterior. . El número de arreglos diagonal-simétricos viene dado por la expresión:
Esta expresión se deriva dividiendo todos los arreglos de torres en clases; en la clase s son aquellos arreglos en los que los pares de torres s no están en diagonal. Exactamente de la misma manera, se puede demostrar que el número de arreglos de n- curvas en un tablero n × n , de manera que no se atacan entre sí y son simétricos a ambas diagonales está dado por las ecuaciones de recurrencia B 2 n = 2 B 2 norte - 2 + (2 norte - 2) B 2 norte - 4 y B 2 norte + 1 = B 2 norte .
Arreglos contados por clases de simetría
Un tipo diferente de generalización es aquella en la que los arreglos de torres que se obtienen entre sí por simetrías del tablero se cuentan como uno. Por ejemplo, si se permite rotar el tablero 90 grados como simetría, cualquier disposición obtenida mediante una rotación de 90, 180 o 270 grados se considera "igual" que el patrón original, aunque estas disposiciones se tengan en cuenta. por separado en el problema original donde se fija la placa. Para tales problemas, Dudeney [11] observa: "Aún no se ha determinado cuántas formas hay si las meras inversiones y reflejos no se cuentan como diferentes; es un problema difícil". El problema se reduce al de contar arreglos simétricos a través del lema de Burnside .
Referencias
- ^ John Riordan , Introducción al análisis combinatorio , Princeton University Press, 1980 (publicado originalmente por John Wiley and Sons, Nueva York; Chapman y Hall, Londres, 1958) ISBN 978-0-691-02365-6 (reimpreso nuevamente en 2002, por Dover Publications). Ver capítulos 7 y 8.
- ^ Weisstein, Eric W. "Polinomio de la torre". De MathWorld - Un recurso web de Wolfram. http://mathworld.wolfram.com/RookPolynomial.html
- ^ Ole J. Heilmann y Elliott H. Lieb, Teoría de los sistemas monómero-dímero. Comunicaciones en física matemática , vol. 25 (1972), págs. 190-232.
- ^ Dudeney, Henry E. Diversiones en matemáticas. 1917. Nelson. (republicado por Plain Label Books: ISBN 1-60303-152-9 , también como colección de recortes de periódicos, Dover Publications, 1958; Editorial Kessinger, 2006). El libro se puede descargar gratuitamente del sitio del Proyecto Gutenberg [1]
- ^ Dudeney, problema 295
- ^ Vilenkin, Naum Ya. Combinatoria (Kombinatorika). 1969. Nauka Publishers, Moscú (en ruso).
- ^ Vilenkin, Naum Ya. Combinatoria popular (Populyarnaya kombinatorika). 1975. Nauka Publishers, Moscú (en ruso).
- ^ Gik, Evgeny Ya. Matemáticas en el tablero de ajedrez (Matematika na shakhmatnoy doske). 1976. Nauka Publishers, Moscú (en ruso).
- ^ Gik, Evgeny Ya. Ajedrez y Matemáticas (Shakhmaty i matematika). 1983. Nauka Publishers, Moscú (en ruso). ISBN 3-87144-987-3 ( GVK-Gemeinsamer Verbundkatalog )
- ^ Kokhas ', Konstantin P. Rook Números y polinomios (Ladeynye chisla i mnogochleny). MCNMO, Moscú, 2003 (en ruso). ISBN 5-94057-114-X www .mccme .ru / free-books / mmmf-lectures / book .26 .pdf ( GVK-Gemeinsamer Verbundkatalog )
- ^ Dudeney, respuesta al problema 295