Cómo muchos patrones distintos son posibles si se omite (a) 1 pieza, (b) 2 piezas (c) 3 piezas de un cubo originalmente compuesto de 27 de menor tamaño y de igual tamaño de los cubos?
Respuestas
¿Demasiados anuncios?
Marko Riedel
Puntos
19255
Vamos a resolver este problema con el Polya Enumeración Teorema. Evidentemente esto es equivalente a contar con dos colores de los cubos pequeños (dejando de lado un cubo es igual para colorear es un segundo, un color diferente). Esto requiere que el ciclo de índice de la permutación grupo $G$ de los pequeños cubos dentro de la grande. Es importante tener en cuenta que nos limitamos a las rotaciones. Si tuviéramos un gráfico en lugar de un objeto del mundo real no sería reflejos de los espejos para tener en cuenta (reflexiones sobre un plano que pasa por el centro del cubo y en paralelo a los dos lados opuestos). Esto no se puede hacer con un objeto concreto. Ahora podemos enumerar las permutaciones de $Z(G)$ por su estructura del ciclo, teniendo en cuenta los tipos de rotaciones en el turno.
Comience con la identidad, lo que contribuye $$a_1^{27}.$$
Ahora hay ocho rotaciones alrededor de ejes de paso a través de las esquinas opuestas del cubo (dos rotaciones por eje, de los cuales hay cuatro), que fijan las tres cubos en la diagonal, y que contribuyen $$8\times a_1^3 a_3^8.$$ Hay tres rotaciones alrededor de ejes de paso a través de los centros de caras opuestas, que a su vez corregir los cubos en dicho eje y que dan $$3\times (2 a_1^3 a_4^6 + a_1^3 a_2^{12}).$$ Por último tenemos las seis rotaciones alrededor de ejes de paso a través de los centros de bordes opuestos, que fijan los cubos del eje y dar $$6\times a_1^3 a_2^{12}.$$ Esto le da el ciclo del índice $A$Z(G) = \frac{1}{24} \left(a_1^{27} + 8\times a_1^3 a_3^8 + 3\times (2 a_1^3 a_4^6 + a_1^3 a_2^{12}) + 6\times a_1^3 a_2^{12}\right)$$ que es $A$Z(G) = \frac{1}{24} \left(a_1^{27} + 8\times a_1^3 a_3^8 + 6\times a_1^3 a_4^6 + 9\times a_1^3 a_2^{12}\right).$$ Ahora, esto da $A$Z(G)(1+z) = 1/24\, \left( 1+z \right) ^{27}+1/3\, \izquierda( 1+z \right) ^{3} \left( 1+{z}^{3} \right) ^{8}\\+1/4\, \izquierda( 1+z \right) ^{3} \left( 1+{z}^{4} \right) ^{6}+3/8\, \left( 1+z \right) ^{3} \left( 1+{z}^{2} \right) ^{12}$$ que es $A$Z(G)(1+z) = {z}^{27}+4\,{z}^{26}+22\,{z}^{25}+139\,{z}^{24}+779\,{z}^{23}+3455\,{z}^{22}\\+12507\, {z}^{21}+37303\,{z}^{20}+92968\,{z}^{19}+195963\,{z}^{18}+352433\,{z}^{17}+544382\,{ z}^{16}\\+725612\,{z}^{15}+837184\,{z}^{14}+837184\,{z}^{13}+725612\,{z}^{12}+544382\, {z}^{11}+352433\,{z}^{10}\\+195963\,{z}^{9}+92968\,{z}^{8}+37303\,{z}^{7}+12507\,{z}^{ 6}+3455\,{z}^{5}\\+779\,{z}^{4}+139\,{z}^{3}+22\,{z}^{2}+4\,z+1,$$ por lo que las respuestas son cuatro, veinte y dos, y ciento treinta y nueve, respectivamente.
Este MSE enlace se calcula la cara llena grupo de permutación de los n-dimensional hipercubo.
Marko Riedel
Puntos
19255
Para que veais la diferencia aquí es un compañero de respuesta que incluye reflexiones en adición a las rotaciones. Este fue el resultado no fue calculada manualmente y el lector es invitado a dar una combinatoria de prueba para los términos del ciclo de índice completo de la simetría del cubo. (Este debe ser factible con el hecho de que el adicional de permutaciones en comparación con las rotaciones sólo se pueden obtener a partir de la anterior mediante la realización de una inversión, pero puede requerir la construcción de un modelo de papel.)
Aquí hemos utilizado el hecho conocido de que las simetrías del hipercubo en $2^n$ vértices son combinaciones de bits volteretas y poco permutaciones, donde los vértices son etiquetados con $n$ cadenas de bits y dos vértices son adyacentes si difieren en un bit. Un poco voltear voltea a algunos fijos subconjunto de la $n$ bits y una permutación permutes ellos. Cada combinación de estos dos produce una permutación de vértices que está garantizado para ser un automorphism. Esto hace que sea fácil para calcular el ciclo de índice, ya que se pueden enumerar de la $2^n \times n!$ permutaciones relativamente rápido para pequeñas $n$ (en contraposición a la búsqueda en el espacio de todas las $(2^n)!$ permutaciones). Tenga en cuenta que hypercubes de dimensiones superiores son definitivamente manejable con este método y se insta al lector a dar a este un intento.
El ciclo de índice $Z(H)$ por el total de las simetrías de la $3\times 3\times 3$ cubo fue encontrado para ser $A$Z(H) = \frac{1}{48} \left( {a_{{1}}}^{27}+9\,{a_{{1}}}^{9}{a_{{2}}}^{9}+9\,{a_{{1}}}^{3}{a_{{2}}}^{12}+a_{{1}}{a_{{2}}}^{13} +8\,{a_{{1}}}^{3}{a_{{3}}}^{8}+6\,{a_{{1}}}^{3}{a_{{4}}}^{6}\\+6\,a_{{1}}a_{{2}}{a_{{4}}}^{6}+8\,a_ {{1}}a_{{2}}{a_{{6}}}^{4}\a la derecha).$$
La generación de funciones de dos patrones de color o, alternativamente, retira los cubos, resulta ser el siguiente $A$Z(H)(1+z) = 1/48\, \left( 1+z \right) ^{27}+3/16\, \izquierda( 1+z \right) ^{9} \left( 1+{z}^{2} \right) ^{9}+1/6 \, \left( 1+z \right) ^{3} \left( 1+{z}^{3} \right) ^{8}\\+3/16\, \left( 1+z \right) ^{3} \left( 1+ {z}^{2} \right) ^{12}+1/8\, \izquierda( 1+z \right) ^{3} \left( 1+{z}^{4} \right) ^{6}+1/6\, \izquierda( 1+ {z}^{6} \right) ^{4} \left( 1+{z}^{2} \right) \left( 1+z \right)\\ +1/8\, \left( 1+{z}^{4} \right) ^{6} \left( 1+{z}^{2} \right) \left( 1+z \right) +1/48\, \left( 1+z \right) \left( 1+{ z}^{2} \right) ^{13}.$$
La expansión da $A$Z(H)(1+z) = {z}^{27}+4\,{z}^{26}+20\,{z}^{25}+101\,{z}^{24} +483\,{z}^{23}+1956\,{z}^{22}+6748\,{z}^{21}\\+19587 \,{z}^{20}+48086\,{z}^{19}+100446\,{z}^{18}+179686\,{z}^{17}+276646\,{z}^{16}+368072\,{z}^{15}\\+ 424308\,{z}^{14}+424308\,{z}^{13}+368072\,{z}^{12}+276646\,{z}^{11} +179686\,{z}^{10}+100446\,{z}^ {9}\\+48086\,{z}^{8}+19587\,{z}^{7}+6748\,{z}^{6}+1956\,{z}^{5} +483\,{z}^{4}+101\,{z}^{3}+20\,{z}^{ 2}+4\,z+1.$$ La secuencia de único color de las $3\times 3\times 3$ $n$ colores que empieza así: $$1, 2852288, 158942078604, 375313061509120, 155221150215953125, 21322735154793366336,$$ que aún no dispone de una OEIS entrada.
Este es el Arce de código que se utilizó en el cálculo. Preguntas y comentarios son bienvenidos como por lo general hay espacio para imrovement en la primera versión de un programa de ordenador. Yo podría haber codificado las representaciones de los cubos pequeños frente a calcular, pero que no podría extrapolarse a hypercubes de dimensiones superiores.
con(numtheory);
con(grupo):
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_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;
cube_vsyms :=
proc()
opción de recordar;
local aut, adj, p, bitstr, bits, b, vsyms, vsym, flip,
doflip, doperm, bits2ind, v1, v2, idx, idxterm,
esquinas, edgemids, centros, cen, censet, c;
bitstr := [];
para b de 0 a 7
bits := convert(8+b, base, 2);
bitstr := [op(bitstr), [seq(bits[k], k=1..3)]];
od;
bits2ind := b -> 1+b[1]+2*b[2]+4*b[3];
vsyms := [];
para pasar de 0 a 7
bits := convert(8+flip, base, 2);
doflip :=
proc(v)
local de res, bpos;
res := [];
para bpos a 3 do
si los bits[bpo] = 1 entonces
res := [op(res), 1-v[bpo]];
otra cosa
res := [op(res), v[bpo]];
fi;
od;
end;
para p en permutar(3)
doperm :=
proc(v)
volver [v[p[1]], v[p[2]], v[p[3]]];
end;
vsym := map(doflip, bitstr);
vsym := map(doperm, vsym);
vsyms := [op(vsyms), mapa(bits2ind, vsym)];
od;
od;
esquinas := [seq(k,k=1..8)];
edgemids := [];
para v1 a 8
para la v2 desde v1+1 a 8
adj :=
proc(b1, b2)
local df;
df := 0;
si b1[1] <> b2[1], a continuación, df := df+1 fi;
si b1[2] <> b2[2], a continuación, df := df+1 fi;
si b1[3] <> b2[3], a continuación, df := df+1 fi;
de regreso en el df
end;
si adj(bitstr[v1], bitstr[v2]) = 1 entonces
edgemids := [op(edgemids), {v1, v2}];
fi;
od;
od;
centros := [];
cen := [[0,0], [0,1], [1, 0], [1, 1]];
para b a 3 do
censet := [];
para c a 4 do
censet :=
[op(censet),
[seq(cen[c][k], k=1..b-1),
0,
seq(cen[c][k], k=b..2)]];
od;
centros :=
[op(centros),
convertir(map(bits2ind, censet), set)];
censet := [];
para c a 4 do
censet :=
[op(censet),
[seq(cen[c][k], k=1..b-1),
1,
seq(cen[c][k], k=b..2)]];
od;
centros :=
[op(centros),
convertir(map(bits2ind, censet), set)];
od;
idx := 0;
para la aut en vsyms ¿
idxterm := 1;
p := [seq(k=aut[k], k=1..nops(aut))];
idxterm :=
idxterm *
pet_autom2cycles(esquinas, subs(p, esquinas));
idxterm :=
idxterm *
pet_autom2cycles(edgemids, subs(p, edgemids));
idxterm :=
idxterm *
pet_autom2cycles(centros de subs(p, centros de));
idx := idx+idxterm*a[1];
od;
idx/nops(vsyms);
end;
v :=
proc(n)
opción de recordar;
local gf, rep;
rep := añadir(cat('X', k), k=1..n);
gf := expand(pet_varinto_cind(rep, cube_vsyms()));
subs([seq(cat('X',k)=1, k=1..n)], gf);
end;
Marko Riedel
Puntos
19255
Para aquellos que estén interesados aquí es una versión de Arce, programa que se ha codificado vértices, aristas y caras. No es portable para mayor dimensión hypercubes pero como el código se reduce considerablemente y la legibilidad de los resultados, con el enfoque en lo esencial.
con(numtheory);
con(grupo):
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_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;
cube_vsyms :=
proc()
opción de recordar;
local aut, adj, p, bitstr, bits, b, vsyms, vsym, flip,
doflip, doperm, bits2ind, v1, v2, idx, idxterm,
esquinas, edgemids, los centros;
bitstr := [];
para b de 0 a 7
bits := convert(8+b, base, 2);
bitstr := [op(bitstr), [seq(bits[k], k=1..3)]];
od;
bits2ind := b -> 1+b[1]+2*b[2]+4*b[3];
vsyms := [];
para pasar de 0 a 7
bits := convert(8+flip, base, 2);
doflip :=
proc(v)
local de res, bpos;
res := [];
para bpos a 3 do
si los bits[bpo] = 1 entonces
res := [op(res), 1-v[bpo]];
otra cosa
res := [op(res), v[bpo]];
fi;
od;
end;
para p en permutar(3)
doperm :=
proc(v)
volver [v[p[1]], v[p[2]], v[p[3]]];
end;
vsym := map(doflip, bitstr);
vsym := map(doperm, vsym);
vsyms := [op(vsyms), mapa(bits2ind, vsym)];
od;
od;
las esquinas := [1, 2, 3, 4, 5, 6, 7, 8];
edgemids := [{1, 2}, {1, 3}, {1, 5}, {2, 4}, {2, 6},
{3, 4}, {3, 7}, {4, 8}, {5, 6}, {5, 7},
{6, 8}, {7, 8}];
centros de := [{1, 3, 5, 7}, {2, 4, 6, 8}, {1, 2, 5, 6},
{3, 4, 7, 8}, {1, 2, 3, 4}, {5, 6, 7, 8}];
idx := 0;
para la aut en vsyms ¿
idxterm := 1;
p := [seq(k=aut[k], k=1..nops(aut))];
idxterm :=
idxterm *
pet_autom2cycles(esquinas, subs(p, esquinas));
idxterm :=
idxterm *
pet_autom2cycles(edgemids, subs(p, edgemids));
idxterm :=
idxterm *
pet_autom2cycles(centros de subs(p, centros de));
idx := idx+idxterm*a[1];
od;
idx/nops(vsyms);
end;
v :=
proc(n)
opción de recordar;
local gf, rep;
rep := añadir(cat('X', k), k=1..n);
gf := expand(pet_varinto_cind(rep, cube_vsyms()));
subs([seq(cat('X',k)=1, k=1..n)], gf);
end;
Aquí hay otro interesante MSE ciclo de índice de cómputo yo. Este MSE ciclo del índice de cálculo II podría ser calificado como lugar exótico.
