16 votos

Colorear las caras de un hipercubo

Voy a repetir el 3-D versión del problema. De cuántas maneras puede el color de un cubo normal con 2 colores hasta una rotación de isometría. La respuesta es, por supuesto, un caso especial de Burnsides Lema que puede ser utilizado para mostrar que el número de los distintos cara permutaciones es $\frac{1}{24}(N^6 + 3N^4 + 12N^3 + 8N^2)$ donde $N$ es el número de colores utilizados, $2$ en este caso, lo que nos da una respuesta de $10$ distintas permutaciones.

Mi pregunta es ¿cómo se puede expandir esto a un teseracto, y, a continuación, de manera más general, a cualquier hipercubo. La rotación de isometrías de un cubo son algo sencillo de comprender, pero la rotación de isometrías o hipercubo son difíciles de comprender (incluso después de una hora de jugar con el 4d rubiks cube app)

Mi idea inicial era la de considerar la expansión de un tesseract como 8 interconectados cubelets. Para el caso de dos colores cada uno de estos cubelets tiene 10 estados distintos. Lo que nos da $10^8$ no distintas permutaciones del hipercubo. O, más en general, esto se reduce a cómo muchas distintas maneras en que uno puede colorear un 8 enfrentado en 3 dimensiones de la figura con 10 colores. Así que la pregunta complicada de 4-dimensional isometrías reduce de 3 dimensiones de rotación de isometrías de un octaedro.

Pero yo soy un físico entonces, ¿qué diablos sé :D

6voto

Matt Dawdy Puntos 5479

Primero vamos al caso especial de Burnside del lema que es relevante aquí.

Lema: Vamos a $G$ ser finito grupo que actúa sobre un conjunto finito $X$. El número de formas de color de los elementos de $X$ $z$ diferentes colores, hasta la acción de la $G$, es

$$\frac{1}{|G|} \sum_{g \in G} z^{c(g)}$$

donde $c(g)$ es el número de ciclos en el ciclo de descomposición de $g$ actuando en $X$. (La prueba.)

Aquí $X$ es el conjunto de caras de un hipercubo. En $n$ dimensiones no se $2n$ de esos rostros. $G$ es el subgrupo de índice $2$ en el hyperoctahedral grupo con determinante $1$, también conocido como el grupo de Coxeter $D_n$. Así que ahora nuestra tarea es la de contar, para cada una de las $k$, el número de elementos de a $D_n$ $k$ ciclos en la acción en $X$.

Ahora, tenga en cuenta que para analizar la acción de $D_n$ en los rostros es suficiente para analizar la acción de $D_n$ en los puntos medios de las caras. Pero estos son precisamente los $2n$$(0, 0, ... \pm 1, ..., 0, 0)$, por lo que escribir los elementos de la $D_n$ firmado permutación de matrices es muy adecuado para el análisis de su acción sobre estos puntos; en particular, es suficiente para encontrar la solución de una sola firmado ciclo. Pero esto resulta ser muy simple: hay uno o dos ciclos, dependiendo de si el producto de los signos es $-1$ o $+1$.

(Puede ser útil aquí para jugar con un ejemplo específico. Considere la posibilidad de $\left[ \begin{array}{cc} 0 & 1 & 0 \\ 0 & 0 & -1 \\ -1 & 0 & 0 \end{array} \right]$ que actúa sobre los seis puntos de $(\pm 1, 0, 0), (0, \pm 1, 0), (0, 0, \pm 1)$ para tener una idea de lo que está pasando en el caso general.)

A partir de aquí creo que es más fácil trabajar con la generación de funciones debido a que la combinatoria ser un poco desordenado. Comenzar con la identidad

$$\sum_{m \ge 0} Z(S_n) t^n = \exp \left( z_1 t + \frac{z_2 t^2}{2} + \frac{z_3 t^3}{3} + ... \right)$$

donde $Z(S_n)$ es el índice de ciclo polinomio para la acción de la $S_n$$\{ 1, 2, ... n \}$. Cada una de las $z_i$ es el término que controla los ciclos de longitud $i$. Queremos modificar la generación de esta función, con lo que se narra cómo los ciclos en $D_n$ trabajo. Hay $2^i$ firmado ciclos de longitud $i$ que vienen en dos sabores: la mitad de ellos tienen signo positivo del producto (dos unsigned ciclos) y la mitad de ellos tienen signo negativo del producto (sin firmar ciclo), así que para mantener un registro del número total de unsigned ciclos debemos remplazar $z_i$$2^{i-1} z^2 + 2^{i-1} z$. También tenemos que tener en cuenta que el determinante de una firma de ciclo es su signo del producto multiplicado por el $(-1)^{i+1}$, y sólo queremos permutaciones con determinante $1$. Por lo que la generación de la función que queremos es

$$\sum_{n \ge 0} f_n(z) \frac{t^n}{n!} = \frac{1}{2} \left( \exp \left( \sum_{i \ge 1} \frac{2^{i-1} z^2 + 2^{i-1} z) t^i}{i} \right) + \exp \left( \sum_{i \ge 1} (-1)^{i+1} \frac{2^{i-1} z^2 - 2^{i-1} z) t^i}{i} \right) \right)$$

donde $f_n(z) = \sum_{g \in D_n} z^{c(g)}$. Después de la simplificación de la anterior se convierte en

$$\sum_{n \ge 0} \frac{1}{|D_n|} f_n(z) t^n = \frac{1}{(1 - t)^{(z^2+z)/2}} + (1+t)^{(z^2-z)/2}.$$

Sustituyendo $z = 2$ da, por fin, la respuesta

$$\sum_{n \ge 0} \frac{1}{|D_n|} f_n(2) t^n = \frac{1}{(1 - t)^3} + 1 + t.$$

En otras palabras, para $n \ge 2$ simplemente tenemos $\frac{1}{|D_n|} f_n(2) = {n+2 \choose 2}$. Esto es una simple respuesta de que debe haber una prueba directa de la misma. Voy a seguir trabajando en él. (Hay una sencilla prueba de la correspondiente resultado con "hipercubo" se sustituye por "simplex," así que supongo que es algo que a lo largo de esas líneas es posible aquí.)

3voto

Kristopher Johnson Puntos 265

Una vez alguien ha hecho el trabajo duro y llegar a la respuesta, como Qiaochu ha hecho, entonces, es fácil demostrar que en un ad hoc la base de este intruso (me).

Considere la posibilidad de una $n$-cubo con caras de color rojo y azul. Considere un conjunto de $n$ bolas. Color de la $j$-ésimo de la bola roja, azul o verde de acuerdo a la los colores de la $j$-ésimo par de caras del cubo, es decir, si ambos tienen el mismo color de darle la pelota que el color, si por el contrario tienen diferentes colores el color de la bola verde. Ahora una operación de simetría en el cubo baraja las bolas de modo que el número de cada uno de los colores de las bolas será el mismo. Por el contrario, dada la $n$ bolas de colores habrá varios colores cubos dando lugar a la distribución del color de las bolas, pero estos todos serán equivalentes en el marco del grupo de simetría del cubo. Sin embargo, para $n\ge 2$ $2$- cubo de color tiene un no-simetría rotacional, así que dos cubos de colores que dan lugar a la misma distribución del color de bolas están relacionados por una rotación. De ahí que el número de $2$color $n$-cubos hasta rotación es el mismo que el número de tripletas $(r,b,g)$ de no negativo enteros adición a $n$ e hay ${n+2\choose 2}$ de estos.

Uno puede repetir este con $k$-colores para el cubo. Esta vez una de las necesidades ${k+1\choose 2}$ los colores de las bolas, y el argumento de garantizar que las rotaciones y la plena grupo de simetría dar la misma respuesta requiere $n>{k\choose 2}$ (żpor qué?).

Añadido(30/9/2010) Uno puede obtener el resultado general el uso de estas consideraciones. Para $n>{k\choose 2}$ uno se $${n+(k^2+k)/2-1\choose (k^2+k)/2-1}$$ las coloraciones hasta las rotaciones. Para $n\le {k\choose 2}$ hay $k$-colorantes no tener impropia (el determinante $-1$) simetrías. Pero la coloración no tiene trivial simetrías. Si dos caras opuestas han el mismo color, se puede reflejar a través de un hyperplane paralelo a ellos. Así que suponer que no hay color es contrario de sí mismo. Entonces, si dos pares de opuestos las caras tienen el mismo dos colores, uno puede reflejar en un avión $x_i=x_j$o $x_i=-x_j$. Por eso, en estos "especiales" coloraciones de cada par de las caras opuestas tiene un par distinto de distintos colores. Hasta simetría hay $${(k^2-k)/2\choose n}$$ de estos colorantes. Así, por $n\le{k\choose 2}$ hay $${(k^2-k)/2\choose n}+{n+(k^2+k)/2-1\choose (k^2+k)/2-1}$$ hasta simetrías de rotación.

2voto

Supongo que usted quiere color de las caras del cubo? Si es así hay $2^6$ colorantes, ya que hay seis caras. Pero, ¿quieres dos colorantes que son equivalentes en virtud de la rotaciones (o rotaciones y reflexiones) a contar como el mismo? Si es así, entonces este es un clásico de la aplicación de Burnside del lexema.

Agregó Si quieres hacer lo mismo en las dimensiones superiores, entonces usted necesita un buen manejar en las simetrías de una $n$-cubo. Su conveniente para el centro de la cubo que se encuentra en el origen y tomar sus vértices para todos los puntos de $(\pm1,\ldots,\pm1)$. A continuación, todas las simetrías del cubo de fijar el origen y sus matrices son "firmado" permutación de matrices: cada fila y columna es cero para guardar una entrada que es $\pm1$. Las rotaciones corresponden a firmado permutación matrices de determinante 1. Los rostros son los conjuntos definidos por $x_i=1$ y $x_i=-1$. De nuevo el uso de Burnside del lema, pero el libro de mantenimiento pone fiddlier.

0voto

Marko Riedel Puntos 19255

Aquí está una contribución de que trata el pleno del grupo de simetría del hipercubo, no rígidos movimientos. Este grupo puede ser obtenida mediante el etiquetado de los vértices del cubo con el $2^n$ cadenas de bits de longitud $n$ donde adyacencia es equivalente a tener un poco diferentes entre dos vértices. A continuación, se obtiene el total de vertex permutación grupo de la hipercubo mediante la combinación de bits mueve de posición de bit permutaciones por ejemplo, combinar un determinado bit flip con un particular permutación de los bits y el resultado es un automorphism. Una vez que tenemos estas permutaciones que podemos utilizar para calcular la inducida por la permutación de grupo en las dos caras.

Esto da el siguiente ciclo de índices para la cara de permutación de grupos que contienen rotaciones y reflexiones: para $n=2,$ $$a_{{1}},$$ para $n=3$, $$1/48\,{a_{{1}}}^{6}+3/16\,{a_{{2}}}^{2}{a_{{1}}}^{2}+1/6\,{a_{{3}}}^{2}+1/16\,{a_{{1 }}}^{4}a_{{2}}+{\frac {7}{48}}\,{a_{{2}}}^{3}+1/8\,{a_{{1}}}^{2}a_{{4}}+1/6\,a_{{6}} +1/8\,a_{{4}}a_{{2}},$$ para $n=4$, $${\frac {1}{384}}\,{a_{{1}}}^{24}+1/32\,{a_{{1}}}^{6}{a_{{2}}}^{9}+1/12\,{a_{{3}}}^{8 }+{\frac {3}{64}}\,{a_{{1}}}^{4}{a_{{2}}}^{10}+{\frac {7}{32}}\,{a_{{4}}}^{5}{a_{{2} }}^{2}+{\frac {1}{96}}\,{a_{{1}}}^{12}{a_{{2}}}^{6}+{\frac {3}{32}}\,{a_{{1}}}^{2}{un _{{2}}}^{11}+1/12\,{a_{{3}}}^{4}{a_{{6}}}^{2}+1/32\,{a_{{1}}}^{4}{a_{{4}}}^{5}+1/16 \,{a_{{1}}}^{2}a_{{2}}{a_{{4}}}^{5}+1/6\,{a_{{6}}}^{4}+1/8\,{a_{{8}}}^{3}+1/32\,{a_{ {4}}}^{6}+{\frac {5}{384}}\,{a_{{2}}}^{12},$$ y para $n=5$, $${\frac {1}{3840}}\,{a_{{1}}}^{80}+{\frac {1}{192}}\,{a_{{1}}}^{20}{a_{{2}}}^{30}+1/ 48\,{a_{{1}}}^{2}{a_{{3}}}^{26}+{\frac {13}{384}}\,{a_{{2}}}^{36}{a_{{1}}}^{8}+{ \frac {37}{192}}\,{a_{{4}}}^{18}{a_{{2}}}^{4}+1/24\,{a_{{1}}}^{2}{a_{{3}}}^{6}{a_{{6 }}}^{10}+1/10\,{a_{{5}}}^{16}+{\frac {1}{768}}\,{a_{{1}}}^{32}{a_{{2}}}^{24}+1/24\,{ a_{{1}}}^{2}{a_{{3}}}^{10}{a_{{6}}}^{8}+1/40\,{a_{{2}}}^{40}+{\frac {1}{192}}\,{a_{{ 1}}}^{8}{a_{{4}}}^{18}+1/32\,{a_{{1}}}^{4}{a_{{2}}}^{2}{a_{{4}}}^{18}+1/24\,{a_{{1}} }^{2}{a_{{3}}}^{2}{a_{{12}}}^{6}+1/8\,{a_{{6}}}^{13}a_{{2}}+1/8\,{a_{{8}}}^{10}+1/10 \,{a_{{10}}}^{8}+{\frac {1}{64}}\,{a_{{1}}}^{4}{a_{{2}}}^{38}+1/48\,{a_{{1}}}^{2}{a_ {{3}}}^{2}{a_{{6}}}^{12}\\+1/32\,{a_{{4}}}^{20}+1/24\,{a_{{12}}}^{6}a_{{6}}a_{{2}} .$$

Estos producen directamente las siguientes fórmulas para el número de colores con en la mayoría de las $N$ colores. Para $n=2$, obtenemos $$N.$$ For $n=3$ obtenemos $$1/48\,{N}^{6}+1/16\,{N}^{5}+3/16\,{N}^{4}+{\frac {13}{48}}\,{N}^{3}+{\frac {7}{24}} \,{N}^{2}+1/6\,N, $$ para $n=4$ tenemos $${\frac {1}{384}}\,{N}^{24}+{\frac {1}{96}}\,{N}^{18}+1/32\,{N}^{15}+{\frac {3}{64}} \,{N}^{14}+{\frac {3}{32}}\,{N}^{13}+{\frac {5}{384}}\,{N}^{12}+1/32\,{N}^{9}+{ \frac {7}{48}}\,{N}^{8}\\+{\frac {7}{32}}\,{N}^{7}+{\frac {11}{96}}\,{N}^{6}+1/6\,{N}^ {4}+1/8\,{N}^{3},$$ y para $n=5$ hemos $${\frac {1}{3840}}\,{N}^{80}+{\frac {1}{768}}\,{N}^{56}+{\frac {1}{192}}\,{N}^{50}+{ \frac {13}{384}}\,{N}^{44}+{\frac {1}{64}}\,{N}^{42}+1/40\,{N}^{40}+1/48\,{N}^{28}+{ \frac {1}{192}}\,{N}^{26}+1/32\,{N}^{24}+{\frac {37}{192}}\,{N}^{22}+{\frac {7}{96}} \,{N}^{20}+1/24\,{N}^{18}+{\frac {29}{240}}\,{N}^{16}+1/8\,{N}^{14}+1/6\,{N}^{10}+{ \frac {17}{120}}\,{N}^{8} .$$ Nota que en el caso de $n=3$ es OEIS A198833.

Estos ciclo de los índices fueron calculados con el siguiente programa Arce.

con(planta, permutar);
con(planta, elija);

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;

hypercube_face_cind :=
proc(dim)
 opción de recordar;

 local verts, v1, v2, caras, f, ff, fv, k, m, b,
 d2, pos, fpos, perm, fperm, actuar, s;

 si dim=1, a continuación, volver a FALLAR fi;

 verts := [];
 para k de 2^dim 2^(dim+1)-1 ¿
 b := convert(k, base, 2);

 verts := [op(verdes), [seq(b[m], m=1..dim)]];
od;

 caras := [];


 para d2 en elegir(dim, 2) hacer
 para k de 2^(dim-2) 2^(dim-1)-1 ¿
 b := convert(k, base, 2);

 f := [];
 para ff en [[0,0], [0,1], [1,0], [1,1]] ¿
 fv := [seq(-1, pos=1..dim)];
 fv[d2[1]] := ff[1];
 fv[d2[2]] := ff[2];

 fpos := 1;
 pos a dim ¿
 si fv[pos] = -1 entonces
 fv[pos] := b[fpos];
 fpos := fpos+1;
fi;
od;

 f := [op(f), fv];
od;

 caras := [op(caras), convertir(f, set)];
od;
od;

 s := 0;
 para k de 2^dim 2^(dim+1)-1 ¿
 b := convert(k, base, 2);

 para perm en permutar(dim) ¿
 act :=
proc(v)
 local w, m;
 w := [seq(v[m], m=1..dim)];
 para m dim ¿
 si b[m]=1 entonces
 w[m] := 1-w[m];
fi;
od;
 w := [seq(w[perm[m]], m=1..dim)]; 
end;

 fperm := map(x -> map(act, x), se enfrenta a);
 s := s + pet_autom2cycles(caras, fperm);
od;
od;

s/2^dim/dim!;
end;



bs_Ninto_cind :=
proc(vN, ind)
 local subs1, indvars, v, bote, res;

 res := ind;

 indvars := indets(ind);
 subs1 := [seq(indvars[k]=vN, k=1..nops(indvars))];

 subs(subs1, res);
end;

v :=
proc(dim)
 opción de recordar;

 bs_Ninto_cind(dim, hypercube_face_cind(dim));
end;

Este MSE enlace calcula otro cubo relacionadas con el ciclo del índice.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X