Hello everyone

I am trying to solve a coloring problem i.e find the number of distinct coloring's of a $\displaystyle n-$beaded necklace with $\displaystyle c$ colors. In doing so I want to derive an equation regarding the number of distinct orbits of a group G which are more applicable than:

$\displaystyle Distinct \: orbits = \frac{1}{\left| G \right|} \sum \limits_{i=1}^{n} \left| Fix(g) \right|, \hspace{0.5cm} g \in G$

In doing so I am considering the coloring of the vertices of a $\displaystyle n-$gon when two coloring's are regard the same if reachable by:


  1. The Cyclic Group $\displaystyle C_n$
  2. The Dihedral Group $\displaystyle D_n$


Acting on the $\displaystyle n-$gon.
So far I have figured out that for the Cyclic group the above (Burnside's Lemma) can be calculated easier as:

$\displaystyle Distinct \: orbits = \frac{1}{\left| G \right|} \sum \limits_{i=0}^{n-1}c^{gcd(i,n)}$

Or put in words the number of colors raised to the number of disjoint-cycles for each permutation. However when I consider the Dihedral Group I find that for the first $\displaystyle \frac{n}{2}$ elements, which are basically the $\displaystyle C_n$ group, I do the same, but for all the elements which can be expressed as an action $\displaystyle r^is$ for $\displaystyle r$ an rotation counterclockwise and $\displaystyle s$ a reflection, I need to add one to the number of disjoint cycles. As an example using $\displaystyle C_6$ and $\displaystyle D_6$ I find the two polynomials.

$\displaystyle P_{C_6}(c) = \frac{1}{6}(c^6+2c+2c^2+c^3)$ for $\displaystyle c=3$ this gives 130

Which makes sense as it fits the number of disjoint cycles, however I also find that:

$\displaystyle P_{D_6}(c) = \frac{1}{12}(c^6+2c+2c^2+c^3+3c^4+3c^3)$ for $\displaystyle c=3$ this gives 92

But for the elements $\displaystyle r^is \in D_6$, I find that the elements are $\displaystyle (1, 3)(4, 6)$, $\displaystyle (1, 5)(2, 4)$, $\displaystyle (2, 6)(3, 5)$, $\displaystyle (1, 2)(3, 6)(4, 5)$, $\displaystyle (1, 4)(2, 3)(5, 6)$ and $\displaystyle (1, 6)(2, 5)(3, 4)$.

So my question is why do I have to add and extra to the number of disjoint cycles to elements $\displaystyle g \in D_n \setminus C_n$.

Thank you