Configuraciones de N azulejos en MxM cuadrícula, hasta rotación de traducción?

Question

Supongamos que tenemos N idéntico 1x1 baldosas a colocar en un MxM tablero de ajedrez:

Ejemplo:

N = 5, M = 4

.X..
X...
..X.
.XX.

Llamamos a esto una configuración. (Claramente hay $M^2$ elija $N$ configuraciones.)

Decimos que dos configuraciones, a y B, son similares si por rotación y/o la traducción de todas las fichas de Un conjunto que puede ser colocado en B configuración.

Por ejemplo, las siguientes tres configuraciones son similares:

....
.XXX
..X.
..X.

XXX.
.X..
.X..
....

....
X...
XXX.
X...

Una configuración de clase es una máxima del conjunto de configuraciones que son similares entre sí. (Claramente la clase de configuración de ningún tipo de configuración es simplemente el cierre bajo rotación y traslación. Además, cada configration clase es, obviamente, distinto de todos los demás.)

Cómo muchos de configuración de clases hay en términos de N y M?

Cualquier idea sobre cómo acercarse a este?

(De fondo: estoy viendo el Juego De la Vida, y el pensamiento acerca de cómo eliminar la búsqueda a partir de las configuraciones que resultan similares progresiones)

Answer 1

Mi solución para el problema requiere de algunos conceptos básicos de la teoría de grupos; el grupo a $D_4$ de las simetrías de la plaza, el grupo de acción, y Burnside del lexema. Si usted no está familiarizado con estos, recomiendo tomar una introducción a la teoría de grupo, o al menos buscar Burnside del lexema.

---

Deje $X$ denota el conjunto de todas las configuraciones de $N$ azulejos en un $M\times M$ red, por lo que el $|X|=\binom{M^2}{N}$. A continuación, $D_4$ actúa de forma natural en $X$, y la configuración de las clases son de lo que luego se llamó órbitas marco de esta acción. Denotamos los elementos de $D_4$ como sigue: $$D_4=\{\operatorname{id},\rho,\rho^2,\rho^3,\sigma,\sigma\rho,\sigma\rho^2,\sigma\rho^3\},$$ donde $\rho$ denota la rotación $\tfrac{\pi}{2}$ radianes, y $\sigma$ la reflexión en cualquier diagonal usted prefiere. A continuación, $\rho^2$ $\rho^3$ son las rotaciones sobre $\pi$ $-\tfrac{\pi}{2}$ radianes, respectivamente, $\sigma\rho^2$ es el reflejo en la otra diagonal. Los restantes dos reflexiones se $\sigma\rho$$\sigma\rho^3$, e $\operatorname{id}$ es la identidad, es decir, "no hacer nada". Podemos contar el número de configuración de las clases o de las órbitas (denotado por $|X/D_4|$) con Burnside del lema, que nos dice que $$|X/D_4|=\frac{1}{|D_4|}\sum_{x\in D_4}|X^x|,$$ donde $X^x$ denota el conjunto de puntos fijos de $x$. Es decir, $|X^x|$ es el número de configuraciones que es invariante bajo $x$. Tenga en cuenta que $|D_4|=8$.

Cada configuración es invariante bajo $\operatorname{id}$, lo $|X^{\operatorname{id}}|=\binom{M^2}{N}$. Computación $|X^x|$ el otro $x\in D_4$ es más trabajo:

En primer lugar, vamos a calcular $|X^{\rho}|$. Si $M$ es par, entonces el $M\times M$ cuadrícula puede ser dividida en cuatro $\tfrac{M}{2}\times\tfrac{M}{2}$ plazas. Si la configuración es invariante bajo $\rho$, entonces la configuración en la parte superior derecha $\tfrac{M}{2}\times\tfrac{M}{2}$ cuadrado determina la configuración completa. Por el contrario, la configuración de la parte superior derecha $\tfrac{M}{2}\times\tfrac{M}{2}$ cuadrado determina una configuración única de la que es invariante bajo $\rho$, y, en particular, el número de baldosas debe ser un múltiplo de $4$, es decir, debemos tener $N\equiv0\pmod4$. Llegamos a la conclusión de que $$|X^{\rho}|=\left\{\begin{array}{cc}\tbinom{M^2/4}{N/4}&\text{ if }N\equiv0\pmod4\\0&\text{ otherwise}\end{array}\right.,$$ si $M$ es incluso. Si $M$ es impar, entonces el $M\times M$ cuadrícula puede ser dividida en cuatro $\tfrac{M-1}{2}\times\frac{M+1}{2}$ rectángulos, leavin una sola ficha en el centro. De nuevo, la configuración es invariante bajo $\rho$ es determinado por la configuración de la parte superior derecha del rectángulo, y cualquier configuración de la parte superior derecha del rectángulo determina una configuración invariantes bajo $\rho$. En particular, cualquiera de las $N\equiv0\pmod4$ o $N\equiv1\pmod4$, dependiendo de si el centro de la baldosa se utiliza o no. Llegamos a la conclusión de que $$|X^{\rho}|=\left\{\begin{array}{cc}\tbinom{(M^2-1)/4}{N/4}&\text{ if }N\equiv0\pmod4\\\tbinom{(M^2-1)/4}{(N-1)/4}&\text{ if }N\equiv1\pmod4\\0&\text{ otherwise}\end{array}\right.,$$ si $M$ es impar. Voy a dejar los valores de $|X^x|$ el otro $x\in D_4$ como un ejercicio, pero aquí están algunas de las expresiones de los mismos en caso de $M$ incluso: \begin{eqnarray*} |X^{\rho^2}|&=&\left\{\begin{array}{cl}\tbinom{M^2/2}{N/2}&\text{ if }N\equiv0\pmod2\\0&\text{ otherwise}\end{array}\right.,\\ |X^{\rho^3}|=|X^{\rho}|&=&\left\{\begin{array}{cl}\tbinom{M^2/4}{N/4}&\text{ if }N\equiv0\pmod4\\0&\text{ otherwise}\end{array}\right.,\\ |X^{\sigma\rho}|=|X^{\sigma\rho^3}|&=&\left\{\begin{array}{cl}\tbinom{M^2/2}{N/2}&\text{ if }N\equiv0\pmod2\\0&\text{ otherwise}\end{array}\right., \end{eqnarray*} Las expresiones para el número de puntos fijos de $\sigma$$\sigma\rho^2$, las reflexiones en las diagonales, no son tan bonitos. Deje $l=\min\{m,n,m-n\}/2$. Entonces $$|X^{\sigma}|=|X^{\sigma\rho^2}|=\left\{\begin{array}{cl}\sum_{K=0}^l\binom{M}{2K}\cdot\binom{M(M-1)/2}{N/2-K}&\text{ if }N\equiv0\pmod2\\\sum_{K=0}^{l-1}\binom{M}{2K+1}\cdot\binom{M(M-1)/2}{(N-1)/2-K} &\text{ if }N\equiv1\pmod2\end{array}\right.,$$ aún suponiendo que $M$ es incluso. Para $M$ impar el resto de los valores de darle un poco más elaborado de expresiones, que voy a dejar como un ejercicio, como la duración de esta respuesta ya está haciendo difícil seguir escribiendo.

Como un ejemplo, para $M=N=4$ como en tu ejemplo, nos encontramos con que \begin{eqnarray*} |X/D_4|&=&\frac{1}{|D_4|}\left(|X^{\operatorname{id}}|+|X^{\rho}|+|X^{\rho^2}|+|X^{\rho^3}|+|X^{\sigma}|+|X^{\sigma\rho}|+|X^{\sigma\rho^2}|+|X^{\sigma\rho^3}|\right)\\ &=&\frac{1}{8}\left(|X^{\operatorname{id}}|+2|X^{\rho}|+3|X^{\rho^2}|+2|X^{\sigma}|\right)\\ &=&\frac{1}{8}\left(\binom{4^2}{4}+2\binom{4^2/4}{4/4}+3\binom{4^2/2}{4/2}+2\sum_{k=0}^2\binom{4}{2k}\binom{4(4-1)/2}{2-k}\right)\\ &=&\frac{1}{8}\left(1820+2\cdot4+3\cdot28+2\cdot(15+36+1)\right)=252 \end{eqnarray*}

EDIT: me acabo de dar cuenta de que su ejemplo se lleva a $M=4$, $N=5$, en cuyo caso las expresiones simplificar de manera significativa. Como antes de encontrar $$|X/D_4|=\frac{1}{8}\left(\binom{16}{5}+2\left(\binom{4}{1}\binom{6}{2}+\binom{4}{3}\binom{6}{1}\right)\right)=567.$$

Answer 2

Me da la impresión de que la primera respuesta no tratar la cuestión de la intención. La acción del grupo diedro $D_4$ en la junta no cumplir con todas las simetrías se muestra en el ejemplo. Yo diría que más bien deberíamos pensar de la junta como un $M\times M$ toro, donde las configuraciones pueden mover horizontal y verticalmente (es decir, ser traducido) así como rotar.

El siguiente Arce programa calcula el ciclo de índice del grupo de simetrías de la $M\times M$ toro para su uso con el Polya Enumeración Teorema.

con(planta):


pet_autom2cycles :=
proc(src, aut)
 numa local, numsubs;
 local de marcas, pos, cycs, cpos, clen;

 numsubs := [seq(src[k]=k, k=1..nops(src))];
 numa := subs(numsubs, aut);

 marcas := [seq(true, pos=1..nops(aut))];

 cycs := []; pos := 1;

 mientras pos <= nops(aut) 
 si las marcas[pos] 
 clen := 0; cpos := pos;

 mientras que las marcas[cpos] ¿
 marcas[cpos] := false;
 cpos := numa[cpos];
 clen := clen+1;
od;

 cycs := [op(cycs), clen];
fi;

 pos := pos+1;
od;

 volver mul(a[cycs[k]], k=1..nops(cycs));
end;



pet_torus_cind :=
proc(M, rot_on)
 opción de recordar;
 local, la putrefacción, rmx, tx, ty, i, j, x, y, xx, yy, res, r;

 si M=1, a continuación, volver a[1] fi;
 si M=2, a continuación, rmx := 1 else rmx := 3 fi;

 si no rot_on y M>1, entonces rmx := 0 fi;

 res := 0;

 para la putrefacción de 0 a rmx ¿
 para el tx de 0 a M-1 hacer
 para ty desde 0 hasta M-1 hacer
 A := [];

 para i desde 0 hasta M-1 hacer
 para j desde 0 hasta M-1 hacer
 x := (i+tx) mod M;
 y := (j+ty) mod M;

 para r a pudrirse ¿
 xx := x; yy := y;
 x := M-1-yy; y := xx;
od;

 A := [op(A), x*M+y];
od;
od;

 res := res+
 pet_autom2cycles([seq(k, k=0..M*M-1)], A);
od;
od;
od;

 volver res/(rmx+1)/M^2;
end;


pet_varinto_cind :=
proc(poli, ind)
 local subs1, subs2, polyvars, indvars, v, bote, res;

 res := ind;

 polyvars := indets(poli);
 indvars := indets(ind);

 para v en indvars ¿
 bote := op(1, v);

 subs1 :=
[seq(polyvars[k]=polyvars[k]^olla,
k=1..nops(polyvars))];

 subs2 := [v=subs(subs1, poli)];

 res := subs(subs2, res);
od;

res;
end;

pet_torus_count :=
proc(M, C, rot_on)
 local ind, gf, vs, k;

 ind := pet_torus_cind(M, rot_on);
 vs := añadir(cat(`X`, k), k=1..C);
 gf := pet_varinto_cind(vs ind);

 subs([seq(cat(`X`, k)=1, k=1..C)], gf);
end;

El programa anterior se puede calcular el ciclo de índices cuando de 90 grados de rotación de la junta está permitido o no permitido. Esto da el siguiente ciclo de dos índices para el caso de $M=4,$ primero, sin rotaciones utilizando traducciones sólo: $$1/16\,{a_{{1}}}^{16}+3/4\,{a_{{4}}}^{4}+3/16\,{a_{{2}}}^{8}$$ y como rotaciones: $${\frac {1}{64}}\,{a_{{1}}}^{16}+{\frac {7}{16}}\,{a_{{4}}}^{4}+{\frac {15}{64}} \,{a_{{2}}}^{8}+1/4\,{a_{{4}}}^{3}{a_{{1}}}^{2}a_{{2}}+1/16\,{a_{{2}}}^{6}{a_{{1 }}}^{4}.$$ Sustituyendo en estos ciclo de índices obtenemos las dos funciones de generación $${z}^{16}+{z}^{15}+9\,{z}^{14}+35\,{z}^{13}+122\,{z}^{12}+273\,{z}^{11}\\+511\,{z}^ {10}+715\,{z}^{9}+822\,{z}^{8}+715\,{z}^{7}+511\,{z}^{6}+273\,{z}^{5}+122\,{z}^{ 4}+35\,{z}^{3}+9\,{z}^{2}+z+1$$ y $${z}^{16}+{z}^{15}+5\,{z}^{14}+11\,{z}^{13}+41\,{z}^{12}+75\,{z}^{11}\\+147\,{z}^{ 10}+189\,{z}^{9}+231\,{z}^{8}+189\,{z}^{7}+147\,{z}^{6}+75\,{z}^{5}+41\,{z}^{4}+ 11\,{z}^{3}+5\,{z}^{2}+z+1.$$ Esto significa que no se $273$ resp. $75$ diferentes configuraciones al $M=4$$N=5$.

También podemos utilizar este programa para calcular el número total de configuraciones toroidales tener $C$ colores. De dos colores con las traducciones, sólo podemos obtener la secuencia de $$2, 7, 64, 4156, 1342208, 1908897152, 11488774559744, 288230376353050816, \\ 29850020237398264483840, 12676506002282327791964489728,\ldots$$ que es A179043 de la OEIS. Como rotaciones tenemos $$2, 6, 28, 1171, 337664, 477339616, 2872202032640, 72057595967392816, \\7462505059899322983424, 3169126500571074529242309120,\ldots$$ Para los tres colores se consigue que dos secuencias $$3, 27, 2211, 2691711, 33891544611, 4169295457320267, 4883659780216684279491, \\53651309692070594433108320631, 5474401089420219382077156686715199875,\ldots$$ y $$3, 21, 627, 678051, 8473285827, 1042324154944641, 1220914945265994019395, \\13412827423019038373526335841, 1368600272355054854637538271201673171,\ldots$$ Finalmente, para el caso especial de $M$ marcas colocadas en un $M\times M$ junta se consigue que dos secuencias $$1, 3, 12, 122, 2130, 54192, 1753080, 69160548, 3220837758, 173103158180,\ldots$$ y $$1, 2, 4, 41, 552, 13786, 438776, 17300202, 805232382, 43276368018,\ldots$$