Understanding and applying Burnside's lemma

Question

Recently I have questioned in here to understand the terms used for expressing Burnside's lemma $|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|$. Someone explained the terms like the following way but I can not understand it.

Here a group $G$ acts on a set $X$. $X/G$ is the quotient of $X$ by $G$; that is, the set of orbits $\{G\cdot x\mid x\in X\}$, or equivalently the set of equivalence classes of $X$ where the equivalence relation is that $x\sim y$ if there is an element $g\in G$ so that $g\cdot x=y$. $X^g$ is the set of fixed points of a group element $g\in G$; i.e. $X^g=\{x\in X\mid g\cdot x=x\}$. So what the equation is saying that the umber of orbits is equal to the average number of fixed points.

I want to solve Necklace problem using Burnside's lemma .What do I need to do or know for intuitive understanding of Burnside's lemma and having capability to apply this lemma to solve the above problem?

Answer 1

Consider a matrix whose columns are indexed by elements of $G$ and whose rows are indexed by elements of $X$ with the property that the entry $(g, x)$ of the matrix is either $1$ or $0$ depending on whether $g$ fixes $x$ or not.

Start with an element $x \in X.$ The sum of the elements of the row $x$ is equals to $|G_x|,$ the stabilizer of $x.$ Also for any $y \in G.x := \{gx | g \in G\},$ the sum of the elements of the row is $y$ is again $|G_y|,$ because $G_x$ and $G_y$ are conjugate. Now $|G/G_x| = |G.x| \Rightarrow$ the sum of all the row-sums, as $y$ varies over a fixed orbit, is $|G|$ and this is independent of orbits. But the orbits partitioned $X$ into disjoint subsets. So the sum of the all the entries of the matrix is $|G| \times r,$ where $r$ is the number of distinct orbits of $X.$

On the other hand, the sum of the elements of a column $g$ is clearly $|X^g|.$ So the sum of the column-sums is $\sum_{g \in G} |X^g|.$

Answer 2

I think first try to see that this sum equal to $1$ if there is only one orbit i.e the action is transitive.

Let the action is transitive, We need to show that

$$\sum_{g\in G}|X^g|=|G|.$$

Note that we are making over sum as $a$ can be element of both $X^{g_1}$ and $X^{g_2}$. How many times we over sum $a$ ?

Not surprisingly, $|Stab(a)|$ times. Since it is true for every elements of $X$, the sum is equal to $|Stab(a)||X|=|G|$. Thus, we are done.

In general, the sum is equal to $|G|$ on every orbits then the result follows.