Polinomio de torre

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 x^k 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.^[1] 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 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. 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í:

R_{B}(x)=\sum _{k=0}^{\infty }r_{k}(B)x^{k}

donde r_k 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 (R_n = R_B) son:

{\begin{aligned}R_{1}(x)&=x+1\\R_{2}(x)&=2x^{2}+4x+1\\R_{3}(x)&=6x^{3}+18x^{2}+9x+1\\R_{4}(x)&=24x^{4}+96x^{3}+72x^{2}+16x+1.\end{aligned}}

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 B_m,n de m × n casillas, se escribe R_m,n := R_{B_m,n} . El menor de m y n puede tomarse como el límite superior para k, ya que obviamente r_k = 0 si k > min(m, n).

Esto también se comprueba 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 generalizado de Laguerre L_n^α(x) por la identidad.

R_{m,n}(x)=n!x^{n}L_{n}^{(m-n)}(-x^{-1}).

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 R_m,n(x) corresponde al gráfico bipartito completo K_m,n . El polinomio de torre de un tablero general B ⊆ B_m,n corresponde al gráfico bipartito con vértices a la izquierda v₁, v₂, ..., v_m y vértices de la derecha w₁, w₂, ..., w_n y un borde v_iw_j 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 r_k, 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 Lieb^[2] 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

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:

{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 polinomio de torre como una generalización del problema de las torres

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 ${\binom {m}{k}}$ maneras. Del mismo modo, el conjunto de k columnas para colocar las torres se puede elegir de ${\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 ${\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]

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 $\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:

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:

{\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.

Disposiciones simétricas

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:

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.

Posiciones contadas según sus clases de simetría

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.

Referencias

↑ 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.
↑ Ole J. Heilmann and Elliott H. Lieb, Theory of monomer-dimer systems. "Comunicaciones en Física Matemática", Vol. 25 (1972), págs. 190-232.
↑ 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 [1]
↑ Dudeney, Problema 295
↑ Vilenkin, Naum Ya. Combinatoria (Kombinatorika). 1969. Nauka Publishers, Moscú (Rusia).
↑ Vilenkin, Naum Ya. Popular Combinatorics (Populyarnaya kombinatorika). 1975. Nauka Publishers, Moscow (In Russian).
↑ Gik, Evgeny Ya. Mathematics on the Chessboard (Matematika na shakhmatnoy doske). 1976. Nauka Publishers, Moscow (In Russian).
↑ Gik, Evgeny Ya. Chess and Mathematics (Shakhmaty i matematika). 1983. Nauka Publishers, Moscow (In Russian). ISBN 3-87144-987-3 (GVK-Gemeinsamer Verbundkatalog)
↑ Kokhas', Konstantin P. Rook Numbers and Polynomials (Ladeynye chisla i mnogochleny). MCNMO, Moscow, 2003 (in Russian). ISBN 5-94057-114-X www.mccme.ru/free-books/mmmf-lectures/book.26.pdf (GVK-Gemeinsamer Verbundkatalog)
↑ Dudeney, Respuesta al problema 295

Datos: Q12594240

[1] 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.

[2] Ole J. Heilmann and Elliott H. Lieb, Theory of monomer-dimer systems. "Comunicaciones en Física Matemática", Vol. 25 (1972), págs. 190-232.

[3] 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 [1]

[4] Dudeney, Problema 295

[5] Vilenkin, Naum Ya. Combinatoria (Kombinatorika). 1969. Nauka Publishers, Moscú (Rusia).

[6] Vilenkin, Naum Ya. Popular Combinatorics (Populyarnaya kombinatorika). 1975. Nauka Publishers, Moscow (In Russian).

[7] Gik, Evgeny Ya. Mathematics on the Chessboard (Matematika na shakhmatnoy doske). 1976. Nauka Publishers, Moscow (In Russian).

[8] Gik, Evgeny Ya. Chess and Mathematics (Shakhmaty i matematika). 1983. Nauka Publishers, Moscow (In Russian). ISBN 3-87144-987-3 (GVK-Gemeinsamer Verbundkatalog)

[9] Kokhas', Konstantin P. Rook Numbers and Polynomials (Ladeynye chisla i mnogochleny). MCNMO, Moscow, 2003 (in Russian). ISBN 5-94057-114-X www.mccme.ru/free-books/mmmf-lectures/book.26.pdf (GVK-Gemeinsamer Verbundkatalog)

[10] Dudeney, Respuesta al problema 295

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]