A modo de respuesta a la pregunta de cómo la Enumeración de Grupos de Potencia a este problema, he conseguido aplicar PGE y, de hecho, esto me ha llevado a revisar parte de mi software PGE. hecho, esto me llevó a revisar parte de mi software PGE, lo que agradezco gracias por ello. PGE permite calcular los cinco primeros valores de $n$ conectores por lado, que son $$2, 35, 2688, 508277, 163715822, \ldots$$
Esto nos lleva a OEIS A132100 donde aprendemos aprendemos que la forma correcta de abordar este problema es a través de un análisis combinatorio que produce una recurrencia bastante simple que puede utilizarse para calcular rápidamente valores grandes.
La técnica de PGE es exactamente la misma que presenté en este MSE enlace al contar subconjuntos de tamaño $k$ de una baraja de cartas bajo permutación de palos.
El repertorio de la función generadora son las aristas que representadas a través del producto de dos variables $U_k U_m$ que indica un borde de $k$ à $m.$ Seleccionamos un subconjunto de $q=4n/2$ de de modo que el grupo que actúa sobre las ranuras es el grupo simétrico $S_q$ actuando en $q$ elementos. El grupo $Q$ que permuta el repertorio es la acción de las cuatro rotaciones del cuadrado sobre las aristas, que contiene cuatro permutaciones sobre $4n(4n-1)/2$ elementos. A continuación, ejecutamos el cálculo habitual de PGE sobre pares de permutaciones $(\alpha,\beta)$ con $\alpha\in S_q$ y $\beta\in Q$ , comprobando si podemos cubrir $\alpha$ con ciclos de $\beta$ y haciendo la contabilidad como descrito en el enlace de la baraja. Las contribuciones en las que un vértice aparece más de una vez no se conservan. (Estas representan un grado de vértice grado de más de uno que no admitimos). El código ha sido optimizado en varios aspectos, en particular la colocación de los ciclos de $\beta$ en $\alpha$ donde la complejidad y la huella de memoria son mucho mejor. Parece notable que un método complejo como PGE pueda implementarse en un programa tan compacto. Es posible una mayor optimización de los dos bucles principales es posible, pero no es probable que se extienda $n$ a seis.
Este es el código de Arce.
with(combinat);
with(numtheory);
pet\_flatten\_term :=
proc(varp)
local terml, d, cf, v;
terml := \[\];
cf := varp;
for v in indets(varp) do
d := degree(varp, v);
terml := \[op(terml), seq(v, k=1..d)\];
cf := cf/v^d;
od;
\[cf, terml\];
end;
pet\_autom2cyclesA :=
proc(src, aut)
local numa, numsubs;
local marks, pos, cycs, data, item, cpos, clen;
numsubs := \[seq(src\[k\]=k, k=1..nops(src))\];
numa := subs(numsubs, aut);
marks := Array(\[seq(true, pos=1..nops(aut))\]);
cycs := \[\]; pos := 1; data := \[\];
while pos <= nops(aut) do
if marks\[pos\] then
clen := 0; item := \[\]; cpos := pos;
while marks\[cpos\] do
marks\[cpos\] := false;
item := \[op(item), aut\[cpos\]\];
cpos := numa\[cpos\];
clen := clen+1;
od;
cycs := \[op(cycs), clen\];
data := \[op(data), item\];
fi;
pos := pos+1;
od;
return \[data, mul(a\[cycs\[k\]\], k=1..nops(cycs))\];
end;
pet\_cycleind\_symm :=
proc(n)
local p, s;
option remember;
if n=0 then return 1; fi;
expand(1/n\*add(a\[l\]\*pet\_cycleind\_symm(n-l), l=1..n));
end;
pet\_perms\_edges :=
proc(n)
option remember;
local cind, p, q, perm, sl,
edges, edgeperm, rotind;
edges :=
\[seq(seq(U\[p\]\*U\[q\], q=p+1..4\*n-1), p=0..4\*n-1)\];
cind := \[\];
for rotind from 0 to 3 do
sl :=
\[seq(U\[p\]=U\[(p+n\*rotind) mod 4\*n\], p=0..4\*n-1)\];
edgeperm := subs(sl, edges);
cind :=
\[op(cind), pet\_autom2cyclesA(edges, edgeperm)\];
od;
cind;
end;
choose\_sum\_prod :=
proc(data, pos, count)
if count = 0 then return 1 fi;
if nops(data) < pos + count -1 then return 0 fi;
choose\_sum\_prod(data, pos+1, count) +
data\[pos\]\*choose\_sum\_prod(data, pos+1, count-1);
end;
tiles :=
proc(n)
option remember;
local idx\_slots, idx\_edges, res, a, b, resA, term,
flat\_a, flat\_b, cycs\_a, cycs\_b, p1, p2, q, v, admit,
tbl\_a, tbl\_b, f1, f2, f3,
cyc, cyc\_set, cyc\_contrib, cyc\_mset;
idx\_slots := pet\_cycleind\_symm(4\*n/2);
idx\_edges := pet\_perms\_edges(n);
res := 0;
for a in idx\_slots do
flat\_a := pet\_flatten\_term(a);
cycs\_a := sort(flat\_a\[2\]);
tbl\_a := table();
for q in convert(cycs\_a, 'multiset') do
tbl\_a\[op(1, q\[1\])\] := q\[2\];
od;
f1 := map(q -> op(1, q), cycs\_a);
f1 := mul(f1\[q\], q=1..nops(cycs\_a));
for b in idx\_edges do
flat\_b := pet\_flatten\_term(b\[2\]);
cycs\_b := sort(flat\_b\[2\]);
tbl\_b := table();
for q in convert(cycs\_b, 'multiset') do
tbl\_b\[op(1, q\[1\])\] := q\[2\];
od;
if tbl\_a\[1\] = 4\*n/2 and
tbl\_b\[1\] = 4\*n\*(4\*n-1)/2 then
res := res +
(4\*n)!/(2^(4\*n/2))/(4\*n/2)!;
next;
fi;
admit := true;
for q in \[indices(tbl\_a, 'nolist')\] do
if not (type(tbl\_b\[q\], integer) and
tbl\_b\[q\] >= tbl\_a\[q\]) then
admit := false;
break;
fi;
end;
if not admit then next fi;
f3 := 1;
for q in \[indices(tbl\_a, 'nolist')\] do
cyc\_set :=
map(cyc->mul(p1, p1 in cyc),
select(cyc->nops(cyc)=q, b\[1\]));
cyc\_contrib :=
choose\_sum\_prod(cyc\_set, 1, tbl\_a\[q\]);
f3 := f3\*tbl\_a\[q\]!\*cyc\_contrib;
od;
f3 := expand(f3);
for v from 0 to 4\*n-1 do
f3 := coeff(f3, U\[v\], 1);
od;
res := res +
f1\*f3\*flat\_a\[1\]\*flat\_b\[1\];
od;
od;
res/4;
end;
1 votos
Crudamente, parece que se podría hacer lo siguiente. Elegir una orientación y etiquetar los puntos de las aristas en el sentido de las agujas del reloj como $1,2,\dots,8$ . Entonces se quiere contar cuántas maneras de emparejar los 8 puntos. Esto es, por supuesto, sólo el coeficiente multinomial $8!/(2!2!2!2!)=7!/2=2520$ . Esto es definitivamente un límite superior en el número de fichas. Creo que se obtiene un límite inferior si se asume que para cada baldosa, las 4 rotaciones posibles son idénticas; entonces habría $7!/8=630$ posibles baldosas. No estoy seguro de que esto sea un límite inferior válido, porque no estoy seguro de si todavía cuenta algo doble.
1 votos
(Cont.) Tratar con el hecho de que diferentes baldosas tienen diferentes grados de simetría rotacional parece un problema difícil en la situación general, que podría tener que abordar con algo de teoría de grupos.
0 votos
Relacionado: math.stackexchange.com/questions/1088313/