Dadas $N,M$ $1 \le M \le 6$ y $1\le N \le 36$. ¿De cuántas maneras podemos ponemos a $N$ caballeros (la mutuamente no atacar) en un tablero de ajedrez de $M \times M$?
Por ejemplo:
$M = 2, N = 2$, ans $= 6$
$M = 3, N = 2$, ans $ = 28$
$M = 6, N = 15$, ans $= 2560$
Es posible solucionar el problema usando la teoría de grafos. Sin embargo, me interesa (más) en una aproximación combinatoria (una solución de forma cerrada).
La respuesta completa a esta pregunta está contenida en los Caballeros polinomios. Por definición, el coeficiente de $q^k$ $m\times n$ caballeros polinomio, $K_{m,n}(q)$, es el número de maneras que $k$ no atacar a los caballeros pueden ser colocados en un $m\times n$ de la junta. Por supuesto, es una tautología decir que esto resuelve el problema, pero hay un algoritmo para calcular. Con este algoritmo, el primeros seis $m\times n$ caballeros polinomios (según su petición)
\begin{align} K_{1,1}(q) &= q+1 \\ K_{2,2}(q) &= q^4+4 q^3+6 q^2+4 q+1 \\ K_{3,3}(q) &= 2 q^5+18 q^4+36 q^3+28 q^2+9 q+1\\ K_{4,4}(q) &= 6 q^8+48 q^7+170 q^6+340 q^5+412 q^4+276 q^3+96 q^2+16 q+1\\ K_{5,5}(q) &= q^{13}+15 q^{12}+158 q^{11}+994 q^{10}+3679 q^9+8526 q^8+12996 q^7+13384 q^6 \\ &+ \; 9386 q^5+4436 q^4+1360 q^3+252 q^2+25 q+1\\ K_{6,6}(q) &= 2 q^{18}+40 q^{17}+393 q^{16}+2560 q^{15}+12488 q^{14}+47684 q^{13}+141969 q^{12} \\ &+ \; 323476 q^{11}+556274 q^{10}+716804 q^9+688946 q^8+491140 q^7+257318 q^6 \\ &+ \; 97580 q^5+26133 q^4+4752 q^3+550 q^2+36 q+1 \end{align}
Tenga en cuenta que estos polinomios de acuerdo con los resultados que proporcionan. Por ejemplo, el coeficiente de $q^{15}$ $K_{6,6}$ es de 2560, correspondientes a su declaración de que $M=6,N=15 \Rightarrow \text{ans} =2560$. Los coeficientes de $q^2$ también está de acuerdo con esta OEIS secuencia.
El algoritmo para el cálculo de ambos es muy similar a la que, obviamente, relacionado con los Reyes problema. Neil Calkin y su REU estudiantes de proporcionar un análisis muy completo de que el problema en dos ponencias en el congreso capitular Numerantium. Shaina Carrera tiene una acceso público a la presentación de sus resultados aquí. He publicado un documento depresentación de una implementación del algoritmo en Mathematica V5. La técnica para contar los caballeros es un poco más complicado, pero utiliza muy similares ideas. Por desgracia, He sido capaz de calcular el $7\times 7$ caballeros polinomio, pero mi equipo los estranguladores en $8\times 8$, el tamaño de un tablero de ajedrez.
En primer lugar, ver OEIS para una lista de números. E. g. Secuencia A172132 cuenta el número de maneras de colocar 2 nonattacking caballeros en un $n\times n$ junta. Nota: este sitio debe estar entre los primeros (además de Google) que usted debe visitar cuando usted tiene un problema combinatorio (como la cuenta).
En segundo lugar, no tengo cerrada "fórmula" para este problema, pero en un algoritmo que se debe trabajar para la entrada de los límites. Dado que el problema es el de un ACM/ICPC naturaleza, supongo que estaría satisfecho con un algoritmo que (cuando se implementa correctamente) daría la respuesta en un tiempo razonable.
Mi algoritmo de programación dinámica (Algunos prefieren "recursividad", porque no es la optimización involucrados. Yo no distinguir aquí.).
Deje $f[i,j,v_{last},v_{second\_last}]$ denotar el número de maneras de colocar $j$ no atacar a los caballeros en la primera $i$ filas de la $n\times n$ junta con la última y la penúltima fila con los estados denotado por $v_{last}$$v_{second\_last}$. Esas son dos de bits en vectores, con 1 siendo un caballero. Así que una fila con dos caballeros en el 2º y el 5º de la célula al $n=5$ será denotado como 01001.
Así que la parte más importante sería la ecuación (estado de transición de la ecuación) $$ f[i,j,v_{pasado},v_{segundo\_last}] = \sum_{v_{tercer\_last}}f[i-1,j-\operatorname{popcount}(v_{pasado}),v_{segundo\_last},v_{tercer\_last}] $$ where $\operatorname{popcount}(v)$ is the number of 1's in bit-vector $v$. Nota los tres vectores deben de ser coherente (no atacar).
Hay, a continuación, $N M 2^{2M}$ estados, y la transición se lleva a otro $2^M$ tiempo, de manera que el algoritmo (si se aplica correctamente) tiene un tiempo de complejidad de $O(N M 2^{3M})$. El obligado no es firme, ya que hay muchas combinaciones no válidas de vectores.
Ver http://oeis.org/A244081 y la facilitan o mi libro http://problem64.beda.cz/silo/kotesovec_non_attacking_chess_pieces_2013_6ed.pdf, página 283-285.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
