Hello everyone

I am trying to solve a coloring problem i.e find the number of distinct coloring's of a n-beaded necklace with 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:

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 n-gon when two coloring's are regard the same if reachable by:


  1. The Cyclic Group C_n
  2. The Dihedral Group D_n


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

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 \frac{n}{2} elements, which are basically the C_n group, I do the same, but for all the elements which can be expressed as an action r^is for r an rotation counterclockwise and s a reflection, I need to add one to the number of disjoint cycles. As an example using C_6 and D_6 I find the two polynomials.

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

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

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

But for the elements r^is \in D_6, I find that the elements are (1, 3)(4, 6), (1, 5)(2, 4), (2, 6)(3, 5), (1, 2)(3, 6)(4, 5), (1, 4)(2, 3)(5, 6) and (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 g \in D_n \setminus C_n.

Thank you