Confusión sobre Burnside ' s lema

Question

En nuestro pregrado de la combinatoria de clase hemos cubierto Burnside del lexema. En nuestras notas de la conferencia declara que:

Supongamos $G$ es de un número finito de permutación grupo que actúa en $A$, y para cada una de las $g\in G$ deje $A^g$ denota el subconjunto de $A$ fijado por $g$. El número de órbitas, denotado $|A/G|$ es

$$|A/G| = \frac{1}{|G|}\sum_{g\in G} |A^g|$$

Estoy muy confundido con un par de puntos debido al hecho de que todavía no he hecho un curso en grupo de teoría (teoría del grupo no es un requisito previo para esta combinatoria de papel) así que nuestra profesora dijo que no necesitamos para entender la notación anterior siempre y cuando sepamos cómo aplicar burnside del lexema mediante el ciclo de términos en el índice etc.

Me gustaría saber en concreto ajuste, lo que el conjunto $A$ es? (O puede darme otro/otro ejemplo). Nuestra profesora demostrado burnside del lexema mediante un doble conteo de argumento y para ayudar a entender lo que el conjunto $A$ nos dio un ejemplo de $A$ siendo el conjunto de todos los $2$ colorantes de un cubo con una cuerda en el centro de una de las caras donde nosotros solo color $4$ de las caras (de modo que la cara opuesta a la cara con la cadena no cuenta en la coloración). Para ilustrar lo que quiero decir tomar este cubo http://uva.onlinejudge.org/external/2/253img1.gif y dicen que la cadena está en la cara $1$ y la cara $6$ no tiene una coloración. Así que sólo por el color de las caras $2,3,4,5$ con el rojo o el azul de decir. Deje $G=\{R_0,R_{90},R_{180},R_{270}\}$ donde $R_0$ es la identidad.

Esto es donde estoy confundido. Pensé que el conjunto de $A$ es un conjunto de los elementos de $G$ act. Así que pensé $A=\{2,3,4,5\}$ en el caso de que el cubo donde los números en el conjunto $A$ se refieren a las caras, no el conjunto de todos los colores del cubo yo.e $A=\{ (R,R,R,R), (R,R,R,B),...,(B,B,B,B)\}$ y, por tanto,$A=|16|$.

Sencillamente, lo de $A$ $A^g$ en términos de conjuntos para el ejemplo anterior o algún otro ejemplo que se puede dar libremente?

Answer 1

Tomemos, por ejemplo, la acción más simple que hay, la acción de la $S_n$ en el conjunto de $X=\{1,\cdots,n\}$ para el que acaba de definir $\sigma\cdot x=\sigma(x)$. Nota luego de que una órbita $\mathcal{O}_x$ $x\in X$ es sólo el conjunto de $\{\sigma(x):\sigma\in S_n\}$. Pero, por supuesto, $\left\{\sigma(x):\sigma\in S_n\right\}$ es sólo $X$! Cualquier elemento de $X$ es golpeado por $\sigma(x)$ algunos $\sigma$. Por lo tanto, ya que esto era cierto para todos los $x$ vemos que el número de órbitas de esta acción es $1$ (todos ellos son sólo una $X$). Por eso, $\#(X/S_n)=1$. Ahora, ¿qué es $X^\sigma$ algunos $\sigma\in S_n$? Por definición, todos los elementos de la $x$ que $\sigma\cdot x=x$ o, en otras palabras, $\sigma(x)=x$. Así, en más de combinatoria notación $X^\sigma=\text{Fix}(\sigma)$. Por lo tanto, el teorema de que no es Burnside nos dice que

$$1=\#(X/S_n)=\frac{1}{|S_n|}\sum_{\sigma\in S_n}\#(X^\sigma)=\frac{1}{n!}\sum_{\sigma\in S_n}\#(\text{Fix}(\sigma))$$

O, dicho de otra manera

$$n!=\sum_{\sigma\in S_n}\#(\text{Fix}(\sigma))$$

Un fresco de la combinatoria hecho en sí de lo que es (al menos para mí) no evidente (hay otra prueba utilizando rep. teoría, aunque).

Si usted está interesado en este tipo de cosas un libro FANTÁSTICO que hará volar tu mente es Algebraicas a Través de la Combinatoria Finita Grupo de Acciones por Mordido et. al Que está disponible gratuitamente aquí.

Answer 2

Al contar el número de diferentes colorantes, el conjunto $A$ describe todos los posibles colores (contando los que pueden ser obtenidos a partir de cada uno de los otros por rotación, simetría, etc. como diferentes).

El grupo $G$ describe exactamente las acciones que hacen dos diferentes colorantes que se considera de la misma: por ejemplo, si desea contar diferentes colorantes de 4 caras del cubo hasta la rotación del cubo, a continuación, $G$ contiene 4 elementos: la rotación del cubo de 0, 90, 180 y 270 grados.

Es importante tener en cuenta que el $G$ debe ser un grupo: la composición de las dos acciones en $G$ debe ser un elemento en $G$. Dicho esto, usted no puede considerar $G$ a sólo 0 o 90 grados de rotación: usted tiene que incluir los otros 2 rotaciones. En términos de permutaciones de los rostros esto significa que se incluyen todos los 4 permutaciones: $(1 2 3 4)^i$ donde $i=0\ldots3$.

También, si usted cuenta con diferentes colorantes hasta simetría así, a continuación, incluir una más de acción en $A$: girar el cubo boca abajo, así como la combinación de esta acción con todos los 4 anteriores: ahora tiene 8 diferentes elementos en $G$. En términos de permutaciones de incluir todos los 8 permutaciones: $(1 2 3 4)^i (2 4)^j$ donde $i=0\ldots 3$ como antes y $j=0\ldots 1$.

Ahora estamos listos para contar todos los colorantes de 4 caras del cubo en 2 colores:

1. Si todos los colorantes son considerados diferentes, $G$ contiene sólo una acción, que es "no hacer nada con el cubo", y todos los elementos de a $A$ son fijados por esta acción. Por lo tanto, usted tiene $\frac{1}{1}(2^4)=16$ diferentes colorantes.

2. Si se tiene en cuenta que los colorantes a la rotación, a continuación, $G$ tiene 4 elementos descritos antes, y $A^{(1 2 3 4)^0}$ (rotación 0) contiene todos los colorantes, $A^{(1 2 3 4)^1}$ $A^{(1 2 3 4)^3}$ (rotaciones de 90 y -90) contienen colorantes tales que todas las 4 caras son de color del mismo color, y $A^{(1 2 3 4)^2}$ (rotación 180) contiene colorantes tal que las caras opuestas son de colores del mismo color. Por lo tanto, usted tiene $\frac{1}{4}(16+2+2+4)=6$ diferentes colorantes hasta las rotaciones.

3. Si usted toma la simetría en cuenta, entonces usted tiene 8 elementos en $G$ y, por un argumento similar, el número de diferentes colorantes hasta rotación y simetría es $\frac{1}{8}(16+2+2+4+8+4+4+8)=6$ así (supongo que por eso).