Quiero colorear un rectángulo de 3x4 usando 2 colores. El número de cuadrados coloreados por cada color debe ser igual a 6. Sin embargo, decimos que dos coloraciones son iguales si se pueden obtener la una de la otra permutando filas o permutando cíclicamente columnas, por ejemplo $$\matrix{1 & 1 & 0 & 1\\0&1&0&1\\1&0&0&0}=\matrix{0&1&0&1\\0&1&1&1\\0&0&1&0}$$ (cambiamos las dos primeras filas y luego movemos las columnas cíclicamente de dos en dos)
La única forma que se me ocurrió para calcularlo fue contar el número total de esas coloraciones $\binom{12}{6}=924$ y dividiéndolo primero por 6 (porque cada coloración tiene 6 formas de ser permutada), y luego por 4 (porque cada coloración tiene 4 permutaciones cíclicas correspondientes diferentes), pero eso claramente no funciona, no sólo porque, por ejemplo $$\matrix{0&1&0&0\\1&1&1&1\\0&1&0&0}$$ tiene sólo 3 permutaciones de filas diferentes, pero también porque 924 no es divisible por 24. Entonces, ¿cuál es la forma adecuada de resolverlo (sin forzar bruscamente todas las 924 coloraciones)?
Respuestas
¿Demasiados anuncios?
La forma de contarlas es utilizando El lema de Burnside .
Primero tienes que averiguar de qué manera puedes transformar uno de tus rectángulos en general. Puedes permutar cíclicamente las columnas de 4 maneras, y permutar las filas de 6 maneras. Puedes combinarlas (en cualquier orden) para obtener 24 formas de transformar un rectángulo. Cada una de esas 24 formas puede o no dar lugar a un patrón diferente. Denotaré la transformación por $[r,c]$ donde $r$ es la permutación de filas, y $c$ es la permutación de la columna.
Para cada una de esas 24 transformaciones $[r,c]$ ahora tienes que contar cuántos de los rectángulos permanecen inalterados.
$[i,i]$ : Es la identidad en la que las filas/columnas no se permutan en absoluto. Todo $\binom{12}{6}=924$ Los rectángulos permanecen igual cuando no se permuta nada.
$[(123),i], [(132),i]$ : Aquí sólo se permutan cíclicamente las filas. Esto significa que cada columna debe tener un solo color. Necesitamos dos columnas de cada color por lo que hay $\binom{4}{2}=6$ rectángulos que permanecen iguales cuando las filas se permutan cíclicamente.
$[i,(1234)], [i,(1432)]$ : Aquí sólo se permutan las columnas un paso en cualquier dirección. Ahora cada fila debe ser de un solo color. Esto no es posible con 6 celdas de cada color, por lo que hay $0$ rectángulos que permanecen igual bajo esta transformación.
$[i,(13)(24)]$ : Ahora las columnas se permutan 2 pasos, por lo que la izquierda $3\times2$ y a la derecha $3\times2$ las mitades del rectángulo deben ser iguales. Cada mitad debe contener 3 de cada color, por lo que hay $\binom{6}{3}=20$ tales rectángulos.
$[(123),(1234)], [(123),(1432)], [(132),(1234)], [(132),(1432)]$ : Aplicar cualquiera de estas transformaciones 3 veces es lo mismo que $[i,(1432)]$ o $[i,(1234)]$ por lo que ningún rectángulo permanece igual bajo esta transformación.
$[(123),(13)(24)], [(132),(13)(24)]$ : Aplicar cualquiera de estas transformaciones 3 veces es lo mismo que $(i,(13)(24))$ y aplicándolo dos veces se obtiene $[(123),i]$ o $[(132),i]$ . Por lo tanto, debe tener columnas alternas, para lo cual hay $2$ posibilidades.
$[(12),i], [(13),i], [(23),i]$ : Aquí las dos filas intercambiadas deben ser iguales. Si la otra fila es de un solo color, entonces hay $2\binom{4}{1}=8$ posibilidades. Si la otra fila tiene dos de cada color, entonces hay $\binom{4}{2}\binom{4}{2}=36$ posibilidades. Así que $44$ en total.
$[(12),(1234)], [(23),(1234)], [(13),(1234)], [(12),(1432)], [(23),(1432)] [(13),(1432)]$ : Aquí la fila estacionaria debe tener un color. Las otras dos filas deben estar formadas por dos mitades iguales, pero esto no es posible con sólo exactamente 6 celdas de cada color.
$[(12),(13)(24)], [(23),(13)(24)], [(13),(13)(24)]$ : Las seis casillas de la mitad izquierda del rectángulo determinan completamente la otra mitad. Debe haber 3 de cada color en cada mitad, por lo que hay $\binom{6}{3}=20$ tales rectángulos.
Los 24 números que obtuvimos son, por tanto, los siguientes $924, 6, 6, 0, 0, 20, 0, 0, 0, 0, 2, 2, 44, 44, 44, 0, 0, 0, 0, 0, 0, 20, 20, 20$ .
El lema de Burnside dice que el número total de rectángulos distintos es la media de estos $24$ números, es decir $(924+2*6+20+2*2+3*44+3*20)/24 = 48$ .
Bueno, una forma es utilizar el lema de conteo de Burnside. Puede haber formas más fáciles, pero me gusta el lema de conteo de Burnside.
Hay, como has señalado, 924 formas de colorear la cuadrícula si se ignora la simetría.
Las simetrías dan una acción de grupo sobre esas 924 coloraciones, quieres contar las órbitas de esa acción.
El lema de conteo de Burnside dice que para contar las órbitas, se puede promediar el número de coloraciones fijadas por cada elemento del grupo.
El grupo de simetría es $S_3\times S_4$ que tiene 144 elementos, así que es mucho trabajo, pero puedes simplificar las cosas un poco como sigue.
En lugar de contar las órbitas de las 924 coloraciones, te das cuenta de que la acción de $S_4$ conserva los recuentos de las columnas, por lo que una coloración con 3 en una columna, 2 en otra, 1 en una tercera columna y 0 en una cuarta columna siempre tendrá esos recuentos, independientemente de cómo permute las filas y las columnas. Así que contaré las coloraciones con esos números de cuadrados coloreados en la primera, segunda, tercera y cuarta columnas respectivamente, y promediaré el número de esas coloraciones fijado por cada elemento de $S_3$ .
Hay ${}^3C_3$ formas de colorear la primera columna, ${}^3C_2$ formas de colorear la segunda columna, ${}^3C_1$ formas de colorear la tercera columna y ${}^3C_0$ formas de colorear la última columna. Eso es un total de $1\times3\times3\times1$ colores. Pero tengo que tener en cuenta las simetrías.
Bueno, $S_3$ tiene seis elementos. Las 9 coloraciones están fijadas por la identidad $i$ .
Tres de los elementos de $S_3$ son transposiciones. Sólo se fija 1 coloración por cualquier transposición.
Dos de los elementos de $S_3$ son ciclos de orden $3$ y no fijan ninguna coloración.
El número medio de coloraciones fijado por los elementos de $S_3$ es $(9+1+1+1+0+0)/6$ que es $2$ .
Del mismo modo, puedes contar las coloraciones cuyos totales de columna son (3,3,0,0), (3,1,1), (2,2,2,0) y (2,2,1,1) para obtener el número total de coloraciones
[la respuesta, por cierto, es 27]
