¿Cuántos patrones únicos se pueden hacer en una cuadrícula de 4x4 teniendo en cuenta la simetría rotacional?

Question

¿Cuántos patrones únicos se pueden hacer en una cuadrícula de 4x4 teniendo en cuenta la simetría rotacional?

Matemáticas
combinatoria
autómata celular

zackit

Estaba trabajando con vecindarios de autómatas celulares Margolus de mayor rango y me encontré con un problema: ¿cuántos patrones se pueden hacer en una cuadrícula cuadrada de 4x4 si se considera que los patrones rotacionalmente simétricos son iguales, pero los patrones simétricos de espejo están separados? además, si alguien pudiera proporcionar una ecuación para calcular cuántos hay en un vecindario NxN arbitrario, sería muy apreciado. Sé que el número total de patrones anisotrópicos es 65536, pero más allá de eso, no estoy seguro.

Respuestas (1)

¿Cuántos patrones únicos se pueden hacer en una cuadrícula de 4x4 teniendo en cuenta la simetría rotacional?

Parcly Taxel · Answer 1

Supongamos que tienes $k$ estados y un $n×n$ red. Hay cuatro automorfismos: el de identidad (fija $k^{n^2}$ rejillas), una $180^\circ$ rotación (arreglos $k^{\lceil n^2/2\rceil}$ rejillas y dos $90^\circ$ rotaciones (arreglar $k^{\lceil n^2/4\rceil}$ cuadrículas cada uno). Por lo tanto, por el lema de Burnside, la respuesta es

\frac{1}{4} (k^{{norte}^{2}} + k^{⌈ {norte}^{2} / 2 ⌉} + 2 k^{⌈ {norte}^{2} / 4 ⌉})

$\frac14(k^{n^2}+k^{\lceil n^2/2\rceil}+2k^{\lceil n^2/4\rceil})$ Para

k = 2

$k=2$ y

n = 4

$n=4$ esto funciona como

\frac{1}{4} (2^{16} + 2^{8} + 2 \cdot 2^{4}) = 16456

$\frac14(2^{16}+2^8+2\cdot2^4)=16456$ .

¡gracias! Voy a esperar para marcar esto como una respuesta para que otros tengan la oportunidad de publicar sus métodos de respuesta, pero esto debería ser bueno.

¿Cuántos patrones únicos se pueden hacer en una cuadrícula de 4x4 teniendo en cuenta la simetría rotacional?

zackit

Respuestas (1)

Parcly Taxel

zackit

Autómatas celulares: ¿Existe un grupo inicial de células en una red cuadrada que nunca se pone a cero por completo?

Nebulosa en Expansión: Problema en Autómatas Celulares o Teoría de Codificación

Personas sentadas alrededor de dos mesas con sillas numeradas

¿Cuál es el número de números de 4 dígitos no crecientes?

¿Cuál es la probabilidad de que una caminata aleatoria que comienza en 0 llegue a +2 en 2 pasos, 3 pasos, 4 pasos, etc.? [duplicar]

Probabilidad de que dos elementos particulares se agrupen en una partición aleatoria con tamaños fijos

Prueba del Teorema de Curtis-Hedlund: ¿Por qué existe una función μ:AS→Aμ:AS→A\mu\colon A^S\to A tal que τ(x)(1G)=μ(x|S)τ( x)(1G)=μ(x|S)\tau(x)(1_G)=\mu(x_{|S}) para todo x∈AGx∈AGx\en A^G?

Demuestra: ∑kk(mk)(nk)=n(m+n−1n)∑kk(mk)(nk)=n(m+n−1n)\sum_k k \binom{m}{k} \binom{ n}{k} = n\binom{m+n-1}{n}

Un gráfico máximo conectado GGG sin ciclos de longitud de al menos k+1k+1k+1 tiene |V(G)|≤k|V(G)|≤k|V(G)| \leq k o tiene un vértice cortado cuando k≥2k≥2k \geq 2

¿Por qué surge esta relación de recurrencia en la que nnn elige kkk? [duplicar]