¿Cuántas de todas las aristas del cubo de 3 colores tienen exactamente 4 aristas de cada color?

Question

I (Decimos que las dos coloraciones son iguales si se puede obtener una segunda girando el cubo y permutando los colores) Mis resualts crédito se dan a la siguiente solución :

Coloración de las aristas del cubo .

[Resumen de la solución : Primero definimos un grupo G, un conjunto X y una acción de grupo de G sobre X. Queremos encontrar el número de coloraciones diferentes de las aristas de un cubo mientras que sabemos que si podemos obtener una coloración girando otra - es la misma coloración. Así que en realidad tenemos que encontrar el número de órbitas de X (la órbita de un elemento x en X es el conjunto de elementos de X a los que x puede ser movido por los elementos de G) y luego usar el lema de Burnside . ]

Por lo tanto, ahora quiero calcular cuántos de los 3 colores que he encontrado tienen exactamente 4 bordes para cada color ?

• esta pregunta se hizo en el curso de Combinatoria como pregunta extra.

Gracias. Bar

Answer 1

Primero construimos la función generadora de las coloraciones de los bordes antes de que el grupo simétrico actúe sobre los colores. Para ello se necesita el índice de ciclo del grupo de permutación de aristas $E$ del cubo. Enumeramos las permutaciones de este grupo por su estructura de ciclos.

En primer lugar, está la identidad, que contribuye $$a_1^{12}.$$

Hay rotaciones alrededor de un eje (tres de ellos) que pasa por el centro de dos caras opuestas, lo que da $$3\times (a_2^6 + 2 a_4^3).$$

Las rotaciones alrededor de una diagonal que pasa por vértices opuestos dan $$4\times 2 a_3^4.$$

Finalmente hay rotaciones de 180 grados alrededor de un eje que pasa por los centros de las aristas opuestas, lo que da $$6\times a_1^2 a_2^5.$$

Esto da el índice de ciclo $$Z(E) = \frac{1}{24} \left(a_1^{12} + 3 a_2^6 + 6 a_4^3 + 8 a_3^4 + 6 a_1^2 a_2^5\right).$$

Sustituyendo en $Z(E)$ obtenemos la siguiente fórmula para el número de $N$ -colores de las aristas de un cubo el valor $$\frac{1}{24}(N^{12} + 3 N^6 + 6 N^3 + 8 N^4 + 6 N^7).$$ Se obtiene la siguiente secuencia $$1, 218, 22815, 703760, 10194250, 90775566, 576941778, 2863870080, 11769161895,\ldots$$ que es OEIS A060530 .

El índice de ciclo sustituido para 3 coloraciones que pide el OP es $$Z(E)(R+G+B)= 1/24\, \left( R+G+B \right) ^{12}+1/8\, \left( {R}^{2}+{G}^{2}+{B}^{2} \right) ^{6}\\+1/4\, \left( {R}^{4}+{G}^{4}+{B}^{4} \right) ^{3}+1/3\, \left( {R}^{3}+{G}^{3}+{B}^{3} \right) ^{4}+1/4\, \left( R+G+B \right) ^{2} \left( { R}^{2}+{G}^{2}+{B}^{2} \right) ^{5}$$ que da como resultado $$[R^4 G^4 B^4]Z(E)(R+G+B)=1479.$$

Anexo a partir de Tue Dec 17 22:50:41 CET 2013. El OP también mencionaba en su consulta que, como giro extra, podemos considerar coloraciones de aristas del cubo en las que el grupo simétrico actúa sobre los colores, de modo que dos coloraciones no sólo son equivalentes cuando hay una rotación que transforma una en la otra, sino también una rotación combinada con una permutación de los colores del grupo simétrico. La técnica para este tipo de problema se denomina Teorema de enumeración de grupos de potencia.

Aquí hay al menos dos enfoques posibles. Está el enfoque clásico del libro Enumeración gráfica de Frank Harary y Edgar Palmer, un texto de referencia que sigue siendo relevante hoy en día. Tienen un capítulo sobre esto, concretamente el capítulo seis, sección cuatro "Enumeración de grupos de potencia / Gráficos con líneas de colores". No voy a mecanografiar aquí sus fórmulas porque no añadiría nada nuevo y el texto está disponible en cualquier biblioteca importante. Sólo diré que tratan el siguiente escenario: enumerar bajo el grupo de potencias las coloraciones de varios grafos, donde una arista puede estar activada o desactivada y tiene $N$ posibles colores en estado activado. Implementé su fórmula en Maple y el resultado fue la siguiente secuencia para coloraciones de aristas del cubo bajo el grupo simétrico que actúa sobre los colores usando como máximo $N$ colores: $$1, 114, 3891, 29854, 87981, 143797, 170335, 177160, 178153, 178243,\ldots$$ Este es el código de Maple para el cálculo Harary/Palmer.

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

pet\_cycleind\_symm :=
proc(n)
        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\_varinto\_power :=
proc(N, ZA)
           local beta, res, indvars, v, t, d, m, pot, ZB;

           ZB := pet\_cycleind\_symm(N);
           if N=1 then ZB := \[ZB\]; fi;

           indvars := indets(ZA);

           res := 0;
           for beta in ZB do
               t := \[\];
               for v in indvars do
                   pot := op(1, v);

                   m := 0;
                   for d in divisors(pot) do
                       m := m +
                       d\*degree(beta, op(0,v)\[d\]);
                   od;

                   t := \[op(t), v=1+m\*z^pot\];
               od;

               res := res+lcoeff(beta)\*subs(t, ZA);
           od;

           res;
end;

cube\_edge\_ind :=
1/24\*(a\[1\]^12+3\*a\[2\]^6+6\*a\[4\]^3+8\*a\[3\]^4+6\*a\[1\]^2\*a\[2\]^5);

vgf :=
proc(N)
         option remember;
         local gf;

         gf := pet\_varinto\_power(N, cube\_edge\_ind);
         expand(gf);
end;

v := N -> coeff(vgf(N), z, 12);

El segundo enfoque utiliza una fórmula diferente de Enumeración de Grupos Potentes (PGET), presentada por Harald Fripertinger en su brillante artículo "Enumeration in Musical Theory" de 1993. Una vez más, no voy a mecanografiar las fórmulas aquí porque no añadiría nada nuevo. La cuestión es que este artículo presenta una forma polinómica del PGET (en el primer capítulo) que permite no sólo calcular el número total de coloraciones, sino también clasificarlas según la distribución de colores utilizada. He implementado esto en Maple y obtengo para la secuencia de coloraciones una vez más los valores (que es como debería ser): $$1, 114, 3891, 29854, 87981, 143797, 170335,\ldots$$ Ahora, sin embargo, también obtenemos las distribuciones de colores. Para dos colores tenemos $$29\,{\it Q6\_Q6}+{\it Q12}+5\,{\it Q2\_Q10}+27\,{\it Q4\_Q8}+{\it Q1\_Q11}+13\,{\it Q3\_Q9}+38\,{\it Q5\_Q7} $$ y para tres colores $$ {\it Q12}+38\,{\it Q5\_Q7}+27\,{\it Q4\_Q8}+{\it Q1\_Q11}+5\,{\it Q2\_Q10}+13\,{\it Q3\_Q9}+370\,{\it Q2\_Q5\_Q5}\\+29\,{\it Q6\_Q6}+600\,{\it Q2\_Q4\_Q6}+236\,{\it Q1\_Q5\_Q6}+85\,{\it Q1\_Q3\_Q8}+77\,{\it Q2\_Q2\_Q8}\\+30\,{\it Q1\_Q2\_Q9}+340\,{\it Q2\_Q3\_Q7}+5\,{\it Q1\_Q1\_Q10}+170\,{\it Q1\_Q4\_Q7}\\+412\,{\it Q3\_Q3\_Q6}+282\,{\it Q4\_Q4\_Q4}+1170\,{\it Q3\_Q4\_Q5}$$ En concreto, ahora estamos en condiciones de responder a la pregunta que motivó el post, que es cuántas coloraciones hay utilizando cada uno de los tres colores cuatro veces, y la respuesta es $$282$$ Aquí están las coloraciones utilizando como máximo cuatro colores: $${\it Q12}+38\,{\it Q5\_Q7}+27\,{\it Q4\_Q8}+{\it Q1\_Q11}+5\,{\it Q2\_Q10}+13\,{\it Q3\_Q9}+370\,{\it Q2\_Q5\_Q5}\\+698\,{\it Q3\_Q3\_Q3\_Q3}+29\,{\it Q6\_Q6}+3480\,{\it Q1\_Q2\_Q4\_Q5}+3510\,{\it Q2\_Q2\_Q3\_Q5}\\+600\,{\it Q2\_Q4\_Q6}+2330\,{\it Q1\_Q3\_Q3\_Q5}+2915\,{\it Q1\_Q3\_Q4\_Q4}+600\,{\it Q1\_Q1\_Q4\_Q6}\\+510\,{\it Q1\_Q2\_Q2\_Q7}+2266\,{\it Q2\_Q2\_Q4\_Q4}+236\,{\it Q1\_Q5\_Q6}+85\,{\it Q1\_Q3\_Q8}\\+ 77\,{\it Q2\_Q2\_Q8}+30\,{\it Q1\_Q2\_Q9}+2320\,{\it Q1\_Q2\_Q3\_Q6}+340\,{\it Q1\_Q1\_Q3\_Q7}\\+13\,{\it Q1\_Q1\_Q1\_Q9}+626\,{\it Q2\_Q2\_Q2\_Q6}+340\,{\it Q2\_Q3\_Q7 }+5\,{\it Q1\_Q1\_Q10}\\+5850\,{\it Q2\_Q3\_Q3\_Q4}+135\,{\it Q1\_Q1\_Q2\_Q8}+170\,{\it Q1\_Q4\_Q7}+412\,{\it Q3\_Q3\_Q6}\\+282\,{\it Q4\_Q4\_Q4}+370\,{\it Q1\_Q1\_Q5\_Q5}+1170 \,{\it Q3\_Q4\_Q5} $$ A continuación figura el código del cálculo Fripertinger.

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

pet\_disjcyc :=
proc(p)
        local dc, pos;

        dc := convert(p, 'disjcyc');

        for pos to nops(p) do
            if p\[pos\] = pos then
                dc := \[op(dc), \[pos\]\];
            fi;
        od;

        dc;
end;

pet\_varinto\_power :=
proc(N, ZA)
        local indvars, delta, v, pot, s, t, poly, k, degs,
                res, cyc;

        indvars := indets(ZA);

        res := 0;
        for delta in permute(N) do
            t := \[\];
            for v in indvars do
                pot := op(1, v);

                s := 0;
                for cyc in pet\_disjcyc(delta) do
                    if pot mod nops(cyc) = 0 then
                        poly :=
                        mul(cat(\`X\`, cyc\[k\])^(pot/nops(cyc)),
                            k=1..nops(cyc));
                        s := s + nops(cyc)\*poly;
                    fi;
                od;

                t := \[op(t), v=s\];
            od;

            res := res+subs(t, ZA);
        od;

        degs :=
        proc(t) local q;
            local vs, v, dl, d, sym;

            vs := indets(t);
            dl := \[\];

            for v in vs do
                dl := \[op(dl), degree(t, v)\];
            od;

            sym := \[\];
            for d in sort(dl) do
                if nops(sym) = 0 then
                    sym := cat(\`Q\`, d);
                else
                    sym := cat(sym, \`\_\`, \`Q\`, d);
                fi;
            od;

            return lcoeff(t)\*sym;
        end;

        if N=1 then
            return cat(\`Q\`, degree(res, \`X1\`));
        fi;

        map(degs, expand(res))/N!;
end;

cube\_edge\_ind :=
1/24\*(a\[1\]^12+3\*a\[2\]^6+6\*a\[4\]^3+8\*a\[3\]^4+6\*a\[1\]^2\*a\[2\]^5);

v :=
proc(N)
        option remember;
        local dist;

        dist := pet\_varinto\_power(N, cube\_edge\_ind);
        map(lcoeff, dist);
end;

Gracias a la OP por plantear una pregunta tan fascinante. He aquí un enlace a una cadena de Cálculos de recuento de Polya .

Anexo a partir de sáb 21 dic 03:20:27 CET 2013 . El algoritmo anterior también se puede utilizar en grafos genéricos y no sólo en cubos. Con dos colores, obtenemos la secuencia $$1, 2, 6, 18, 78, 522, 6178, 137352, 6002584, 509498932, 82545586656, 25251015686776,\ldots$$ que es OEIS A007869 . Tres colores intercambiables producen la secuencia $$1, 3, 15, 142, 4300, 384199, 98654374, 70130880569, \\136638863494089, 730439999032117301,\ldots$$ que aún no tiene entrada en la OEIS. Con cuatro colores intercambiables obtenemos $$1, 3, 22, 513, 67685, 37205801, 74992370359, 543437207831908, 14224090440652751128,\ldots $$ El cálculo de los índices cíclicos pertinentes se muestra a continuación Enlace MSE . Este Enlace MSE II muestra Power Group Enumeration con el grupo de volteo que actúa sobre las ranuras.

Adenda 13 dic 2016. Al lector le interesará saber que estas funciones generadoras también pueden calcularse a partir de primeros principios a saber, el lema de Burnside, como se hizo en el MSE enlace . El algoritmo está documentado allí y en las páginas enlazadas. Presento este algoritmo aquí como referencia. La salida hasta el orden de clasificación es la misma que la del cálculo Fripertinger.

with(combinat);

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, 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))\]);

    pos := 1; data := table();

    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\]\];

                clen := clen+1;
                cpos := numa\[cpos\];
            od;

            if type(data\[clen\], 'list') then
                data\[clen\] :=
                \[op(data\[clen\]), item\];
            else
                data\[clen\] := \[item\];
            fi;
        fi;

        pos := pos+1;
    od;

    return data;
end;

pet\_flatten\_automcycs :=
proc(tbl)
local res, sz, cyc;
    res := \[\];

    for sz in \[indices(tbl, 'nolist')\] do
        for cyc in tbl\[sz\] do
            res := \[op(res), cyc\];
        od;
    od;

    res;
end;

cube\_edge\_cind :=
1/24\*(a\[1\]^12 + 8\*a\[3\]^4 + 6\*a\[4\]^3 + 3\*a\[2\]^6 + 6\*a\[1\]^2\*a\[2\]^5);

cube\_edge\_colorings :=
proc(n)
option remember;
local idx\_colors, res, a, b,
    flat\_a, flat\_b, cyc\_a, cyc\_b, len\_a, len\_b, p, q,
    src, perm, acycs, gf, msetgf, term, deg, rep;

    res := 0; src := \[seq(el, el=1..n)\];

    for a in cube\_edge\_cind do
        flat\_a := pet\_flatten\_term(a);

        perm := firstperm(n);
        while type(perm, \`list\`) do
            acycs := pet\_autom2cyclesA(src, perm);
            flat\_b := pet\_flatten\_automcycs(acycs);

            p := 1;
            for cyc\_a in flat\_a\[2\] do
                len\_a := op(1, cyc\_a);
                q := 0;

                for cyc\_b in flat\_b do
                    len\_b := nops(cyc\_b);

                    if len\_a mod len\_b = 0 then
                        q := q +
                        len\_b\*mul(Q\[el\], el in cyc\_b)
                        ^(len\_a/len\_b);
                    fi;
                od;

                p := p\*q;
            od;

            res := res + p\*flat\_a\[1\];

            perm := nextperm(perm);
        od;
    od;

    gf := expand(res/n!);
    msetgf := 0;

    for term in gf do
        rep := 0;

        for deg in
        sort(map(Q-> degree(term, Q),
                 convert(indets(term), \`list\`)))
        do
            if type(rep, \`integer\`) then
                rep := cat(\`Q\`, deg);
            else
                rep := cat(rep, \`\_Q\`, deg);
            fi;
        od;

        msetgf := msetgf + lcoeff(term)\*rep;
    od;

    msetgf;
end;