¿Cuántos patrones únicos existen para una cuadrícula de $N\times N$?

Question

Estoy tratando de averiguar si hay una forma de determinar cuántos patrones únicos existen para una cuadrícula de $N\times N$ si se eligen N puntos en la cuadrícula. Por ejemplo, para una cuadrícula de $2\times 2$ podemos obtener dos patrones únicos de las seis combinaciones posibles. El resto son simplemente rotaciones e inversos de los dos patrones únicos a continuación

[x] [x]

[ ] [ ]

y

[x] [ ]

[ ] [x]

¿Existe una forma matemática de determinar un número único de patrones para una cuadrícula NxN donde N=3,4,5,6,7,8?

Calculé que para un 3x3, hay 14 patrones únicos para elegir 3 puntos aleatorios en la cuadrícula, pero se vuelve tedioso después de eso.

N:   N^2 : N^2 Elija N Patrón único
2    4     6            2           
3    9     84           14           
4    16    1820         ????         
5    25    53130        ????        
6    36    1947792      ????        
7    49    85900584        ????        

Answer 1

De hecho, podemos hacer un poco más y calcular el índice de ciclos $Z(G_N)$ para $N$ general, donde tenemos que distinguir entre $N$ par y $N$ impar. Esto permitirá búsqueda en la OEIS, lo que a su vez conduce a más material sobre este interesante problema.

Procedemos a enumerar las permutaciones de $G_N$ por su estructura de ciclos. Para $N$ par, obtenemos la identidad, que contribuye $$a_1^{N^2}.$$ Hay una reflexión vertical, que contribuye $$a_2^{N^2/2},$$ lo mismo para una reflexión horizontal, es decir $$a_2^{N^2/2}.$$ La reflexión en la diagonal ascendente contribuye $$a_1^N a_2^{(N^2-N)/2},$$ lo mismo para la otra diagonal, es decir $$a_1^N a_2^{(N^2-N)/2}.$$

Lo que queda son las rotaciones. Dos de éstas contribuyen (recordemos que $N$ es par) $$2\times a_4^{N^2/4}$$ y una de ellas, $$a_2^{N^2/2}.$$ Esto da para un $N$ par el índice de ciclos $$Z(G_N) = \frac{1}{8} \left( a_1^{N^2} + 3 a_2^{N^2/2} + 2 a_1^N a_2^{(N^2-N)/2} + 2 a_4^{N^2/4}\right).$$ Para $N$ impar, obtenemos la identidad, que es $$a_1^{N^2}.$$ Las dos reflexiones ahora contribuyen $$2\times a_1^N a_2^{(N^2-N)/2}.$$ La reflexión en las dos diagonales no cambia y contribuye $$2\times a_1^N a_2^{(N^2-N)/2}$$ Lo que queda son las rotaciones, dos de las cuales tienen estructura de ciclo $$2\times a_1 a_4^{(N^2-1)/4}$$ y la última tiene estructura de ciclo $$a_1 a_2^{(N^2-1)/2}.$$

Esto da para un $N$ impar el índice de ciclos $$Z(H_N) = \frac{1}{8} \left( a_1^{N^2} + 4 a_1^N a_2^{(N^2-N)/2} + 2 a_1 a_4^{(N^2-1)/4}+a_1 a_2^{(N^2-1)/2}\right).$$ Evidentemente para $N$ marcas colocadas en la cuadrícula buscamos calcular $$[z^N] Z(G_N)(1+z) \quad\text{y}\quad [z^N] Z(H_N)(1+z),$$ alternando entre los dos para $N$ par y $N$ impar.

Esto produce la secuencia $$1, 2, 16, 252, 6814, 244344, 10746377, 553319048, 32611596056, 2163792255680,\ldots$$ que es A019318 de la OEIS.

Aquí está el programa Maple que se utilizó para calcular estos índices de ciclos.

with(numtheory);
with(group):
with(combinat):

pet\_varinto\_cind :=
proc(poly, ind)
           local subs1, subs2, polyvars, indvars, v, pot, res;

           res := ind;

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

           for v in indvars do
               pot := op(1, v);

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

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

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

           res;
end;

G :=
proc(N)
        if type(N,odd) then return FAIL; fi;

        1/8\*(a\[1\]^(N^2)+3\*a\[2\]^(N^2/2)+
        2\*a\[1\]^N\*a\[2\]^((N^2-N)/2) + 2\*a\[4\]^(N^2/4));
end;

H :=
proc(N)
        if type(N,even) then return FAIL; fi;

        1/8\*(a\[1\]^(N^2)+4\*a\[1\]^N\*a\[2\]^((N^2-N)/2)+
        a\[1\]\*a\[2\]^((N^2-1)/2) + 2\*a\[1\]\*a\[4\]^((N^2-1)/4));
end;

v :=
proc(N)
        option remember;
        local p, k, gf;

        if type(N, even) then
            gf := expand(pet\_varinto\_cind(1+z, G(N)));
        else
            gf := expand(pet\_varinto\_cind(1+z, H(N)));
        fi;

        coeff(gf, z, N);
end;

Aquí hay otro cómputo de índices de ciclos de MSE I interesante. Este cómputo de índices de ciclos de MSE II también es relevante.

Answer 2

He aquí una respuesta que conduce a la explícita fórmulas cuya más complicado término es una suma, un producto de los coeficientes binomiales. Todavía no he hecho ningún intento de conectar a los excelentes soluciones en las respuestas dadas anteriormente.

Primero un poco de notación. El diedro del grupo de la plaza, $D_4,$ tiene elementos $\{e,\rho,\rho^2,\rho^3,h,v,d_1,d_2\},$ donde $e$ es la identidad, $\rho$ $90^\circ$ rotación, $h$ es la reflexión sobre el eje horizontal, $v$ es la reflexión sobre el eje vertical, $d_1$ es la reflexión sobre el avance de la diagonal, y $d_2$ es la reflexión acerca de la diagonal hacia atrás.

(Agregado: no Habiendo aprendido Pólya enumeración correctamente, hice mi respuesta demasiado complicado. Os dejo mi respuesta anterior, pero se añade una ruta más directa a la ecuación (**) que aparece a continuación. En este problema tenemos $D_4$ que actúa sobre el conjunto de $X,$ que consiste en la $\binom{n^2}{n}$ formas de colorear $n$ pequeños cuadrados en la $n\times n$ rejilla negro, dejando el resto de los cuadros en blanco. La órbita de contar teorema lleva inmediatamente a (**) desde $$ K(n)=\lvert\mathcal{S}\rvert=\frac{1}{8}\sum_{g\en D_4}C(n,n,\langle g\rangle) $$ es idéntica a la de (**) cuando uno se da cuenta de que $\langle\rho\rangle=\langle\rho^3\rangle=C_4.$ La órbita de contar teorema se describe en muchos lugares. Para mayor comodidad he anexado poco de información de fondo acerca a la final de este post.)

Puesto que el orden de $D_4$ $8,$ todos los subgrupos son de orden $1,$ $2,$ $4,$ o $8.$ Cualquiera de los dos elementos de orden $4,$ $\rho$ y $\rho_3,$ genera $C_4,$ la rotación del grupo de la plaza. Cada uno de los cinco elementos de orden $2$, $\rho^2,$ $h,$ $v,$ $d_1,$ y $d_2,$ genera un subgrupo de orden $2.$ Hay otros dos subgrupos de orden $4,$ isomorfo a $C_2\times C_2.$ son $\{e,\rho^2,h,v\}$ $\{e,\rho^2,d_1,d_2\}.$ Cualquier otro grupo generado por dos elementos de orden $2$ es de $D_4.$

Hay, por tanto, $10$ subgrupos con inclusiones dada por el siguiente diagrama de Hasse.

Definir $C(n,b,G)$ a ser el conjunto de configuraciones de la $n\times n$ cuadrícula con $b$ marcado plazas que son invariantes bajo el grupo de $G.$ Que son en última instancia los interesados en $b=n,$, pero se iniciará con la ligeramente mayor generalidad. Definir $\overline{C}(n,b,G)$ a ser el subconjunto de $C(n,b,G)$ compuesto de elementos que no son invariantes bajo cualquier grupo que si bien contiene $G.$ El número que desea calcular, que denotamos $K(n),$ es $$ \begin{aligned} (*)\quad K(n)=&\frac{\lvert\overline{C}(n,n,D_4)\rvert}{1}+\frac{\lvert\overline{C}(n,n,\{e,\rho^2,h,v\})\rvert}{2}+\frac{\lvert\overline{C}(n,n,C_4)\rvert}{2}+\frac{\lvert\overline{C}(n,n,\{e,\rho^2,d_1,d_2\})\rvert}{2}\\ &+\frac{\lvert\overline{C}(n,n,\{e,h\})\rvert}{4}+\frac{\lvert\overline{C}(n,n,\{e,v\})\rvert}{4}+\frac{\lvert\overline{C}(n,n,\{e,\rho^2\})\rvert}{4}+\frac{\lvert\overline{C}(n,n,\{e,d_1\})\rvert}{4}\\ &+\frac{\lvert\overline{C}(n,n,\{e,d_2\})\rvert}{4}+\frac{\lvert\overline{C}(n,n,\{e\})\rvert}{8}. \end{aligned} $$

(Agregado: El conjunto de $C(n,n,G)$ es el conjunto de los colorantes cuyo estabilizador contiene $G,$ mientras $\overline{C}(n,n,G)$ es el conjunto de los colorantes cuyo estabilizador es igual a $G.$ La fórmula (*) por $K(n),$ el número de órbitas, viene contando cada uno de colorear con un peso igual al recíproco del tamaño de su órbita, el peso de haber sido calculada utilizando la órbita-estabilizador teorema. (Ver al final del post.) Por ejemplo, si $x$ tiene estabilizador $D_4,$, entonces el peso es $1/1=8/8;$ si $x$ tiene estabilizador $\{e,\rho^2,h,v\},$, entonces el peso es $1/2=4/8.$ De curso, como se señaló anteriormente, el uso de (*) y la inclusión-exclusión argumento a continuación se representa superfluo por la utilización de la órbita de contar teorema. Es interesante que a pesar de (*) involucra a todos los diez subgrupos de $D_4,$ la expresión final (**) sólo implica a los siete subgrupos cíclicos. Mi ingenuo derivación no explica esto, pero la órbita de contar teorema de hace manifiesto que ese debe ser el caso.)

En el diagrama, podemos obtener expresiones para la $\overline{C}(n,b,G)$ en términos de la $C(n,b,G):$ $$ \begin{aligned} \lvert\overline{C}(n,b,D_4)\rvert&=\lvert C(n,b,D_4)\rvert\\ \vert\overline{C}(n,b,\{e,\rho^2,h,v\})\rvert&=\lvert C(n,b,\{e,\rho^2,h,v\})\rvert- \lvert C(n,b,D_4)\rvert\\ \vert\overline{C}(n,b,C_4)\rvert&=\lvert C(n,b,C_4)\rvert- \lvert C(n,b,D_4)\rvert\\ \vert\overline{C}(n,b,\{e,\rho^2,d_1,d_2\})\rvert&=\lvert C(n,b,\{e,\rho^2,d_1,d_2\})\rvert- \lvert C(n,b,D_4)\rvert\\ \vert\overline{C}(n,b,\{e,h\})\rvert&=\lvert C(n,b,\{e,h\})\rvert- \lvert C(n,b,\{e,\rho^2,h,v\})\rvert\\ \vert\overline{C}(n,b,\{e,v\})\rvert&=\lvert C(n,b,\{e,v\})\rvert- \lvert C(n,b,\{e,\rho^2,h,v\})\rvert\\ \vert\overline{C}(n,b,\{e,d_1\})\rvert&=\lvert C(n,b,\{e,d_1\})\rvert- \lvert C(n,b,\{e,\rho^2,d_1,d_2\})\rvert\\ \vert\overline{C}(n,b,\{e,d_2\})\rvert&=\lvert C(n,b,\{e,d_2\})\rvert- \lvert C(n,b,\{e,\rho^2,d_1,d_2\})\rvert\\ \vert\overline{C}(n,b,\{e,\rho^2\})\rvert&=\lvert C(n,b,\{e,\rho^2\})\rvert- \lvert \overline{C}(n,b,\{e,\rho^2,h,v\})\rvert- \lvert \overline{C}(n,b,C_4)\rvert\\ &\quad- \lvert \overline{C}(n,b,\{e,\rho^2,d_1,d_2\})\rvert- \lvert \overline{C}(n,b,D_4)\rvert\\ &=\lvert C(n,b,\{e,\rho^2\})\rvert- \lvert C(n,b,\{e,\rho^2,h,v\})\rvert- \lvert C(n,b,C_4)\rvert\\ &\quad- \lvert C(n,b,\{e,\rho^2,d_1,d_2\})\rvert+2 \lvert C(n,b,D_4)\rvert\\ \vert\overline{C}(n,b,\{e\})\rvert&=\lvert C(n,b,\{e\})\rvert- \lvert \overline{C}(n,b,\{e,h\})\rvert- \lvert \overline{C}(n,b,\{e,v\})\rvert- \lvert \overline{C}(n,b,\{e,\rho^2\})\rvert\\ &\quad- \lvert \overline{C}(n,b,\{e,d_1\})\rvert- \lvert \overline{C}(n,b,\{e,d_2\})\rvert- \lvert \overline{C}(n,b,\{e,\rho^2,h,v\})\rvert\\ &\quad- \lvert \overline{C}(n,b,C_4)\rvert- \lvert \overline{C}(n,b,\{e,\rho^2,d_1,d_2\})\rvert- \lvert \overline{C}(n,b,D_4)\rvert\\ &=\lvert C(n,b,\{e\})\rvert- \lvert C(n,b,\{e,h\})\rvert- \lvert C(n,b,\{e,v\})\rvert- \lvert C(n,b,\{e,\rho^2\})\rvert\\ &\quad- \lvert C(n,b,\{e,d_1\})\rvert- \lvert C(n,b,\{e,d_2\})\rvert+2\lvert C(n,b,\{e,\rho^2,h,v\})\rvert\\ &\quad+2\lvert C(n,b,\{e,\rho^2,d_1,d_2\})\rvert \end{aligned} $$ Esto implica que $$ \begin{aligned} (**)\quad K(n)=&\frac{\lvert C(n,n,C_4)\rvert}{4}+\frac{\lvert C(n,n,\{e,h\})\rvert}{8}+\frac{\lvert C(n,n,\{e,v\})\rvert}{8}+\frac{\lvert C(n,n,\{e,\rho^2\})\rvert}{8}\\ &+\frac{\lvert C(n,n,\{e,d_1\})\rvert}{8}+\frac{\lvert C(n,n,\{e,d_2\})\rvert}{8}+\frac{\lvert C(n,n,\{e\})\rvert}{8}. \end{aligned} $$

Sigue para calcular las cantidades $C(n,b,G)$ para los siete grupos que aparecen en la expresión anterior. (Agregado: es habitual en Pólya enumeración en este punto en el ciclo de índice y la generación de la función de las técnicas. Mi más con las manos desnudas enfoque de los rendimientos de la final expresiones de una forma bastante directa de la moda.) Tenemos $$ C(n,b,\{e\})=\binom{n^2}{b}. $$ En general, el recuento depende de si $n$ es par o impar. Si $n$ es impar, entonces la acción de la $C_4$ corrige el centro de la plaza; todos los demás plaza tiene una órbita de tamaño $4.$ por lo Tanto, una configuración que es invariante bajo la acción de $C_4$ es especificado por la elección de la marca del centro de la plaza y de uno de los cuadrados de cada una de las $\frac{n^2-1}{4}$ órbitas de tamaño $4.$ (Las otras tres plazas en una órbita de tamaño $4$ deben ser marcados de la misma manera que la primera plaza.) Dado que el número total de plazas debe ser $b,$ hemos $$ C(n,b,C_4)=\begin{cases}\binom{(n^2-1)/4}{b/4} & \text{if %#%#%}\\ \\ \binom{(n^2-1)/4}{(b-1)/4} & \text{if %#%#%}\\ \\ 0 & \text{otherwise.}\end{casos} $$ El centro de la plaza está sin marcar al $b\equiv0\pmod{4}$ y marcó al $b\equiv1\pmod{4}$ Si $b\equiv0\pmod{4}$ es incluso entonces, bajo la acción de $b\equiv1\pmod{4}.$ cada cuadrado tiene una órbita de tamaño $n$ por lo Tanto $$ C(n,b,C_4)=\begin{cases}\binom{n^2/4}{b/4} & \text{if %#%#%}\\ \\ \binom{n^2/4}{(b-1)/4} & \text{if %#%#%}\\ \\ 0 & \text{otherwise.}\end{casos} $$ Especializada a $C_4,$ tenemos $$ C(n,n,C_4)=\begin{cases}\binom{n^2/4}{n/4} & \text{if %#%#%}\\ \\ \binom{(n^2-1)/4}{(n-1)/4} & \text{if %#%#%}\\ \\ 0 & \text{otherwise.}\end{casos} $$

El análisis de la $4.$ es similar. La órbita tamaños son ahora $b\equiv0\pmod{4}$ en lugar de $b\equiv1\pmod{4}$, con la excepción de el centro de la plaza en la $b=n,$ extraño caso, que tiene la órbita tamaño de $n\equiv0\pmod{4}$ El resultado, por $n\equiv1\pmod{4}$ es $$ C(n,n,\{e,\rho^2\})=\begin{cases}\binom{n^2/2}{n/2} & \text{if %#%#% even}\\ \\ \binom{(n^2-1)/2}{(n-1)/2} & \text{if %#%#% odd.}\end{casos} $$

Al $G=\{e,\rho^2\}$ $2$ es impar, la acción de la $4,$ corrige el $n$ plazas en la línea central horizontal. Todas las demás plazas de la órbita tamaño de $1.$ Una configuración invariantes bajo la acción de $b=n,$ es especificado por el marcado $n$ de estas órbitas y $n$ plazas en la línea central. Al $G=\{e,h\}$ es aún, todos los cuadrados tienen órbita tamaño de $n$, por lo que sólo necesitamos mark $G$ de estas órbitas. El análisis de al $n$ es similar. En el $2.$ de los casos, esto da $$ C(n,n,\{e,h\})=C(n,n,\{e,v\})=\begin{cases}\binom{n^2/2}{n/2} & \text{if %#%#% even}\\ \\ \sum_j\binom{(n^2-n)/2}{j}\binom{n}{n-2j} & \text{if %#%#% odd.}\end{casos} $$

Al $\{e,h\}$ o $j$ es una diagonal que es fijado por la acción de la $b-2j$ por Lo que el análisis es el mismo que para $n$ $2,$ impar. Tenemos $$ C(n,n,\{e,d_1\})=C(n,n,\{e,d_2\})= \sum_j\binom {n^2-n)/2}{j}\binom{n}{n-2j}. $$ Mathematica reconoce esta suma, que denotamos por a $b/2$ como una función hipergeométrica generalizada con el argumento de $G=\{e,v\}$ $$ S=\sum_j\binom {n^2-n)/2}{j}\binom{n}{n-2j} = \ _3F_2\left[\begin{matrix}1/2-n/2 & -n/2 & (n-n^2)/2\\1/2 & 1 & \end{de la matriz};-1\right]. $$ De hecho, $$ \begin{aligned} S=&\sum_j\binom{(n^2-n)/2}{j}\binom{n}{n-2j} =\sum_j\binom{(n^2-n)/2}{j}\binom{n}{2j}\\ =&\sum_j\frac{\frac{n^2-n}{2}(\frac{n^2-n}{2}-1)\ldots(\frac{n^2-n}{2}-j+1)}{j!}\frac{n(n-1)\ldots(n-2j+1)}{2j(2j-1)\ldots1}\\ =&\sum_j\frac{n-n^2}{2}\left(\frac{n-n^2}{2}+1\right)\ldots\left(\frac{n-n^2}{2}+j-1\right)\frac{\frac{-n}{2}\frac{-n+1}{2}\ldots\frac{-n+2j-1}{2}}{j(j-\frac{1}{2})\ldots\frac{2}{2}\frac{1}{2}}\frac{(-1)^j}{j!}\\ =&\sum_j\frac{n-n^2}{2}\left(\frac{n-n^2}{2}+1\right)\ldots\left(\frac{n-n^2}{2}+j-1\right)\\ &\times\frac{\frac{-n}{2}\left(\frac{-n}{2}+1\right)\ldots\left(\frac{-n}{2}+j-1\right)\frac{1-n}{2}\left(\frac{1-n}{2}+1\right)\ldots\left(\frac{1-n}{2}+j-1\right)}{\frac{1}{2}\frac{3}{2}\ldots\left(\frac{1}{2}+j-1\right)\cdot1\cdot2\ldots\cdot j}\frac{(-1)^j}{j!}, \end{aligned} $$ que, por definición, es la indicada función hipergeométrica generalizada.

La combinación de estos resultados, hemos $$ K(n)=\begin{cases} \frac{1}{8}\binom{n^2}{n} + \frac{1}{4}\binom{n^2/4}{n/4} + \frac{3}{8}\binom{n^2/2}{n/2} + 
\frac{1}{4}S & \text{for %#%#%}\\ \frac{1}{8}\binom{n^2}{n} + \frac{1}{4}\binom{(n^2-1)/4}{(n-1)/4} + \frac{1}{8}\binom{(n^2-1)/2}{(n-1)/2} + 
\frac{1}{2}S & \text{for %#%#%}\\ \frac{1}{8}\binom{n^2}{n} + \frac{3}{8}\binom{n^2/2}{n/2} + 
\frac{1}{4}S & \text{for %#%#%}\\ \frac{1}{8}\binom{n^2}{n} + \frac{1}{8}\binom{(n^2-1)/2}{(n-1)/2} + 
\frac{1}{2}S & \text{for %#%#%} \end{casos} $$ Esta respuesta coincide con la de Marko Riedel y la OEIS secuencia que él cita. (Añadido: Estas fórmulas pueden ser obtenidos sin mucha dificultad por la extracción de la correspondiente coeficiente de la última generación de la función de Marko Riedel de la respuesta.)

Agregado: (Algunos antecedentes acerca de la órbita-estabilizador y teorema de la órbita de contar teorema.) Deje $b=n$ ser un grupo que actúa sobre un conjunto $n$. El estabilizador de $n$ es el conjunto de elementos de $G=\{e,d_1\}$ que arreglar $\{e,d_2\},$ es decir, el conjunto de $G.$ tal que $G=\{e,h\}$ La órbita de $n$ es el conjunto de elementos de $S,$ que $-1:$ es enviado por algún elemento de $n\equiv0\pmod{4}$

La órbita-estabilizador teorema establece que, para cualquier $n\equiv1\pmod{4}$ $$ \lvert G\rvert=\lvert\text{órbita}(x)\rvert\cdot\lvert\text{stabilizier}(x)\rvert. $$ Es una consecuencia del hecho de que $n\equiv2\pmod{4}$ es un subgrupo de $n\equiv3\pmod{4}.$ y el hecho de que los elementos de la $G$ están en una correspondencia uno a uno con la izquierda cosets de $X.$

La acción de la $x\in X$ $G$ particiones $x,$ en discontinuo de las órbitas. Deje $g\in G$ el conjunto de las órbitas. El conjunto fijo de $gx=x.$ es el conjunto de elementos de $x\in X$ fijado por $X$ es decir, el conjunto de $x$ tal que $G.$ La órbita de contar teorema, que es a menudo llamado Burnside del lexema, establece que el número de órbitas es igual a la media (sobre todos los $x\in X,$) $\text{stabilizer}(x)$ es probado por el teniendo en cuenta el conjunto $G$ de pares $\text{orbit}(x)$ satisfacción $\text{stabilizer}(x).$ Podemos contar los elementos de $G$, ya sea mediante la ejecución de más de $X$ o a correr por encima de $X$ $$ \begin{aligned} \lvert P\rvert=\sum_{g\in G}\lvert\text{fixed}(g)\rvert&=\sum_{x\in X}\lvert\text{stabilizer}(x)\rvert\\ &=\sum_{x\in X}\frac{\lvert G\rvert}{\lvert\text{orbit}(x)\rvert}\\ &=\lvert G\rvert\sum_{O\in\mathcal{O}}\sum_{x\in O}\frac{1}{\lvert\text{orbit}(x)\rvert}\\ &=\lvert G\rvert\sum_{O\in\mathcal{O}}1\\ &=\lvert G\rvert\cdot\lvert\mathcal{O}\rvert, \end{aligned} $$ donde la órbita-estabilizador teorema se utiliza para obtener la segunda línea. Esto implica que $$ \lvert\mathcal{S}\rvert=\frac{1}{\lvert G\rvert}\sum_{g\in G}\lvert\text{solucionado}(g)\rvert, $$ cual es el resultado deseado.

Answer 3

Estás buscando el número de órbitas del grupo diedral $D_N$ actuando en la grilla $N\times N$ con $N$ celdas seleccionadas. (Precaución: este grupo a menudo se expresa como $D_{2N}$ ya que tiene $2N$ elementos.)

Quieres usar el Lema de Cauchy-Frobenius-Burnside (también conocido como Lema de Burnside, también conocido como "No es el Lema de Burnside") para calcular esto. Es decir, tienes una acción de grupo de $D_N$ sobre el conjunto $\Omega$ de todos estos patrones (grillas $N\times N$ con $N$ celdas marcadas), y el número de órbitas en esta acción (que es lo que quieres) está dado por $$\frac{1}{2N}\sum_{g\in G} |\Omega^g|$$ donde $|\Omega^g|$ es el número de elementos en $\Omega$ fijados por $g$.

Answer 4

Considera la acción del grupo $G$ en un conjunto $\Omega$ de cardinalidad $n$. El índice de ciclo de $(G,\Omega)$ es el polinomio definido por $$Z_G(X_1,X_2,\dots, X_n)=\frac{1}{|G|} \sum_{g\in G} X_1^{c_1(g)}X_2^{c_2(g)}\cdots X_n^{c_n(g)}$$ donde $c_i(g)$ denota el número de $i$-ciclos en la descomposición en ciclos del elemento $g$ actuando en $\Omega$.

Por ejemplo, si consideramos la acción de $D_4$ en el cuadrado, primero etiquetaríamos los vértices del cuadrado como $\{1,2,3,4\}$ en algún orden. Vamos a hacer esto en orden cíclico en sentido horario, comenzando desde la esquina superior izquierda. Entonces obtenemos la siguiente tabla. \begin{array}{c|c|c} g & \mbox{permutación} & \mbox{término del índice de ciclo}\\ \hline \mbox{identidad} & (1)(2)(3)(4) & X_1^4 \\ 90^o \mbox{rotación} & (1,2,3,4) & X_4^1 \\ 180^o \mbox{rotación} & (1,3)(2,4) & X_2^2 \\ 270^o \mbox{rotación} & (1,4,3,2) & X_4^1 \\ \mbox{reflexión horizontal} & (1,4)(2,3) & X_2^2\\ \mbox{reflexión vertical} & (1,2)(3,4) & X_2^2\\ \mbox{reflexión diagonal} & (1,3)(2)(4) & X_1^2X_2\\ \mbox{reflexión diagonal opuesta} & (2,4)(1)(3)& X_1^2X_2 \end{array>

Así obtenemos como índice de ciclo $$Z_G(X_1,X_2,\dots, X_n)=\frac{1}{8}(X_1^4 + 2X_1^2X_2+3X_2^2+2X_4).$$

Ahora considera $$Z_G(b+1,b^2+1,b^3+1,b^4+1).$$ El coeficiente de $b^i$ dará el número (¡hasta isomorfismo!) de posiciones en las que hay precisamente $i$ cuadrados marcados. Volviendo al problema de la cuadrícula, solo nos interesa el coeficiente del término $b^2$. Esto resulta ser $\frac{1}{8}(16) = 2$.

Answer 5

http://puzzlemaker.discoveryeducation.com/MathSquareForm.asp

Aquí tienes un enlace a un creador de puzzles llamado Math Square.

Te permite crear puzles de matrices.

Por ejemplo, puedes crear una cuadrícula de 6x6 y las filas y columnas son ecuaciones matemáticas que contienen multiplicación, división, suma y resta. Las respuestas a las ecuaciones están disponibles en la parte extrema derecha y en la parte extrema inferior de la cuadrícula. Sin embargo, ningún número en la cuadrícula está proporcionado. ¿Se puede resolver lógica o matemáticamente dicho puzle utilizando alguno de los métodos mencionados en este hilo?