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?
Best Answer
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.