And here is an explanation:
First, read this:
http://en.wikipedia.org/wiki/Burnside%27s_lemmaIf you don't know all of the terms, that's okay, just read the example application and it will probably make sense. Burnside's lemma is pretty intuitive I think.
Anyway, the (1/n) is because there are n possible rotations. Then, the summation term thing (which was being called x earlier, I will probably continue to do this) is the number of cycles with n/d-symmetry. (for example, a regular hexagon has 1-symmetry, 2-symmetry, 3-symmetry, and 6-symmetry).
A cycle is invariant under a rotation by k/n revolutions if and only if the cycle has gcd(k,n) symmetry. The number of k ≤ n such that gcd(k,n) = d is equal to phi(n/d), which explains one of the phi(n/d) in the summation term.
So, we need to count the number of cycles with d-symmetry. For odd n, this is (((d - 1)! / 2)((n / d)^(d - 1))phi(n / d).
Notice that if the graph has d-symmetry, if vertex a is linked to vertex b, then vertex a + d is linked to vertex a + d + b (where the vertices are labeled in order and the labels are taken modulo n). So, we can divide the vertices into d groups of n/d vertices. If d > 1, then no vertex can be linked to any vertex in its own group, because then its group would just become a cycle by itself (this is the step which is false if n is even).
Now, if a vertex in group A is linked to a vertex in group B, then all of the vertices in group A are linked to a vertex in group B. So, the ways all of the groups are linked form a cycle of their own, which I'll call a group-cycle. Since there are d groups, there are (d - 1)! / 2 possible group cycles.
Now we need to count the number of cycles you can form given a certain group-cycle. Say d = 5 and our group cycle is A to B to C to D to E and back to A. Then, starting with a vertex in group A, we have n/d choices of what vertex to link to in B, then n/d choices for what to link to in C, then n/d choices for what to link to in D, and finally n/d choices for what to link to in E, for (n/d)^(d - 1) total possible choices (so far).
Now, how many ways are there to link back to A? If we link back to the wrong vertex in A, for example if we link back to the vertex we started with, then we will get multiple cycles rather than one big cycle. Label the vertices of group A in order as 0, 1, 2, ... n/d - 1, where 0 is the vertex we started with and the labels are taken modulo n/d. Say the vertex we link back to is vertex m. Then, as we go from vertex m to a vertex in B and then a vertex in C and so on, when we get back to group A again, we will land on vertex 2m. And if we do that again, we will land on 3m, 4m, etc. until we land on 0 again. Now, if m is not relatively prime to n/d, there will be some vertices of A which we never landed on, so we would not have a full cycle. Therefore we must pick a vertex m such that m and n/d are relatively prime; there are phi(n/d) ways to do this.
Multiplying all that stuff together, we get ((d - 1)! / 2)((n / d)^(d - 1))phi(n / d) cycles with d-symmetry.
Finally, the case where d = 1 is pretty straightforward and similar to what we just did. Label the vertices 0, 1, 2, ..., n - 1 and the labels are taken modulo n. If 0 is linked to m, then m is linked to 2m, and so on, until we get back to 0. This will only produce a full cycle if m is relatively prime to n, so there are phi(n) valid choices of m. However, linking 0 to m results in the same cycle as linking 0 to -m, so we actually only have phi(n)/2 choices. Fortunately phi(n)/2 = ((1 - 1)! / 2)((n / 1)^0)phi(n / 1), so we don't need to special case this in our summation.
Now, we just apply Burnside's Lemma to get (1/n)(Sum of ((d - 1)! / 2)((n / d)^(d - 1))phi(n / d)^2 over all d such that d|n)
Since that probably was not clear at all, feel free to ask questions.