Confusion concerning Burnside's Lemma
In our undergraduate combinatorics class we covered Burnside's lemma. In our lecture notes it states that:
Suppose $G$ is a finite permutation group which acts on $A$, and for each $g\in G$ let $A^g$ denote the subset of $A$ fixed by $g$. The number of orbits, denoted $|A/G|$ is
$$|A/G| = \frac{1}{|G|}\sum_{g\in G} |A^g|$$
I'm quite confused with a few points due to the fact that I haven't yet done a course on group theory (group theory is not a prerequisite for this combinatorics paper) so our lecturer said that we don't need to understand the notation above as long as we know how to apply burnside's lemma using cycle index terms etc.
I'd like to know in a concrete setting, what the set $A$ is? (Or you can give me a different/another example). Our lecturer proved burnside's lemma using a double counting argument and to help as understand what the set $A$ he gave us an example of $A$ being the set of all $2$ colorings of a cube with a string on the center of one of the faces where we color only $4$ of the faces (so the face opposite the face with the string doesn't count in the colouring). To illustrate what I mean take this cube http://uva.onlinejudge.org/external/2/253img1.gif and say the string is on face $1$ and face $6$ doesn't have a coloring. So we only color the faces $2,3,4,5$ with either red or blue say. Let $G=\{R_0,R_{90},R_{180},R_{270}\}$ where $R_0$ is the identity.
This is where I'm confused. I thought the set $A$ is a set the the elements of $G$ act on. So I thought $A=\{2,3,4,5\}$ in the case of the cube where the numbers in the set $A$ refer to the faces, not the set of all colorings of the cube i.e $A=\{ (R,R,R,R), (R,R,R,B),...,(B,B,B,B)\}$ and hence $A=|16|$.
Simply put, what do $A$ and $A^g$ look like in terms of sets for the example above or some other example that you may freely give?
Solution 1:
Take for example the simplest action there is--the action of $S_n$ on the set $X=\{1,\cdots,n\}$ for which you just define $\sigma\cdot x=\sigma(x)$. Note then that an orbit $\mathcal{O}_x$ of $x\in X$ is just the set $\{\sigma(x):\sigma\in S_n\}$. But, of course $\left\{\sigma(x):\sigma\in S_n\right\}$ is just $X$! Any element of $X$ is hit by $\sigma(x)$ for some $\sigma$. Thus, since this was true for all $x$ we see that the number of orbits of this action is $1$ (they are all just $X$). So, $\#(X/S_n)=1$. Now, what is $X^\sigma$ for some $\sigma\in S_n$? By definition it's all the elements of $x$ for which $\sigma\cdot x=x$ or, in other words, $\sigma(x)=x$. So, in more combinatorial notation $X^\sigma=\text{Fix}(\sigma)$. Thus, the theorem that is not Burnside's tells us that
$$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))$$
Or, said differently
$$n!=\sum_{\sigma\in S_n}\#(\text{Fix}(\sigma))$$
A cool combinatorial fact within itself which is (at least to me) non-obvious (there is another proof using rep. theory though).
If you are interested in this sort of things a FANTASTIC book that will blow your minds is Algebraic Combinatorics Via Finite Group Actions by Bitten et. al It is freely available here.
Solution 2:
When you are counting the number of different colorings, the set $A$ describes all possible colorings (counting those that can be obtained from each other by rotation, symmetry etc. as different).
The group $G$ describes exactly those actions that make two different colorings considered the same: for example, if you want to count different colorings of 4 faces of the cube up to rotation of the cube, then $G$ contains 4 elements: rotation of the cube by 0, 90, 180 and 270 degrees.
It is important to note that $G$ must be a group: the composition of two actions in $G$ must be an element in $G$. That being said, you cannot consider $G$ to be just 0 or 90 degree rotation: you have to include the other 2 rotations as well. In terms of permutations of the faces this means that you include all 4 permutations: $(1 2 3 4)^i$ where $i=0\ldots3$.
Also, if you are counting different colorings upto symmetry as well, then you include one more action on $A$: rotating the cube upside down, as well as the combination of this action with all 4 previous: now you have 8 different elements in $G$. In terms of permutations you include all 8 permutations: $(1 2 3 4)^i (2 4)^j$ where $i=0\ldots 3$ as before and $j=0\ldots 1$.
Now we are ready to count all colorings of 4 faces of the cube in 2 colors:
If all colorings are considered different, then $G$ contains just one action, which is "do nothing with the cube", and all elements of $A$ are fixed by this action. Therefore, you have $\frac{1}{1}(2^4)=16$ different colorings.
If you count colorings up to rotation, then $G$ has 4 elements as described before, and $A^{(1 2 3 4)^0}$ (rotation by 0) contains all colorings, $A^{(1 2 3 4)^1}$ and $A^{(1 2 3 4)^3}$ (rotations by 90 and -90) both contain colorings such that all 4 faces are colored the same color, and $A^{(1 2 3 4)^2}$ (rotation by 180) contains colorings such that the opposite faces are colored the same color. Therefore, you have $\frac{1}{4}(16+2+2+4)=6$ different colorings upto rotations.
If you take the symmetry into consideration, then you have 8 elements in $G$ and, by a similar argument, the number of different colorings upto rotation and symmetry is $\frac{1}{8}(16+2+2+4+8+4+4+8)=6$ as well (guess why).