Using the orbit-stabilizer theorem to count graphs Revising for a course in group and representation theory, I have come across the following interesting problem:

Use the orbit-stabilizer theorem to compute the number of isomorphism classes of simple (i.e. undirected, no multiple edges, no short loops) graphs with $n$ vertices.

I have tried for a while, but I didn't find the correct group to make act on the $n$-graphs $\Gamma_n$. My only conclusion until now is that the correct action of the mysterious group $G$ should commute with the action of $S_n$ making the vertices commute (since two graphs are in the same equivalence class if they are in the same orbit of said action).
Any hints/ideas?
 A: You want $G=S_n$ acting on the edges of the complete graph, I believe. Rather than just Orbit-Stabilizer, this version is usually called Pólya's enumeration theorem. It is just a fancy version of orbit-stabilizer, but pretty fancy in my opinion.
The number of simple graphs is tabulated in OEIS:A000088.
The cases $n=3$ and $n=4$ are worked in detail at wikipedia (page 1) and wikipedia (page 2).
In the  GAP computer algebra software, you can use the following code. For $n\leq 1$ the lack of edges appears to confuse it. There are 1 graphs for $n=0$, 1 for $n=1$. You can use genfunc to sort the graphs by how many edges they have, or just count to sum them up. The Value function just substitutes values for each variables, $t_i =a_i \mapsto 1+t^i$ in genfunc and then $t\mapsto 1$ in count.

gap> t := X(Rationals,"t":old);;
gap> genfunc := n -> Value(
> CycleIndex( SymmetricGroup(n), Combinations([1..n],2), OnSets ),
> List([1..Binomial(n,2)],i->X(Rationals,i)),
> List([1..Binomial(n,2)],i->(1+t^i)));;
gap> count := n -> Value( genfunc(n), [t], [1] );;
gap> List([2..11],count);
[ 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168, 1018997864 ]

In case you want to use Jim's method, it can calculate up to $n=20$ in the same time the by-the-definition-of-PET method goes to $n=11$:

gap> CountBelk := n -> Sum( Partitions(n), p ->
> 2^( Sum(p,ki->Int(ki/2)) + 
> Sum(Combinations([1..Size(p)],2),ij->Gcd(p{ij})) )
> / Product( Collected(p), i_ci -> Factorial(i_ci[2]) * i_ci[1]^i_ci[2] )
> );;
gap> List( [2..20], CountBelk );

The weird division thing is actually multiplying by the size of the conjugacy class, and the entire thing is divided by the order of $S_n$. I just left out both the multiply and the divide by Factorial(n).
A: Let $G$ be a group acting on a set $X$.  Burnside's Lemma says that
$$
|X/G| \;=\; \frac{1}{|G|} \sum_{g\in G} |X^g|,
$$
where $X/G$ is the set of orbits in $X$ under $G$, and $X^g$ denotes the set of elements of $X$ fixed by the element $g$.  This lemma follows fairly immediately from the Orbit-Stabilizer Theorem (see the short proof in the Wikipedia article).
Using Burnside's lemma, it is not too hard to count the isomorphism classes of graphs with $n$ vertices.  Let $E$ be the set of $\binom{n}{2}$ edges of a complete graph with $n$ vertices.  Then any graph $\Gamma$ with $n$ vertices corresponds to a subset of $E$, i.e. a function $f_\Gamma\colon E\to \{0,1\}$.
Given any permutation $\sigma \in S_n$ of the $n$ vertices, let $\sigma_E$ be the corresponding permutation of the elements of $E$.  Then a graph $\Gamma$ is stabilized by $\sigma$ if and only if $f_\Gamma$ is constant on the edges of each cycle of $\sigma_E$.  Thus, the number of graphs stabilized by $\Gamma$ is $2^{N(\sigma_E)}$, where $N(\sigma_E)$ denotes the number of cycles in $\sigma_E$.  By Burnside's Lemma, it follows that the number of isomorphism classes is
$$
\frac{1}{|S_n|}\sum_{\sigma\in S_n} 2^{N(\sigma_E)}
$$
Example:  Let's compute the number of graphs with four vertices.  The group $S_4$ has five different types of elements:


*

*The identity element,

*Six two-cycles,

*Eight three-cycles,

*Six four-cycles, and

*Three elements of the form $(*\;\;*)(*\;\;*)$


Obviously $N(\sigma_E) = |E| = 6$ if $\sigma$ is the identity element.  If $\sigma=(1\;2)$, then $\sigma_E$ has four cycles:
$$
\sigma_E \;=\; \bigl(\{1,2\}\bigr)\;\bigl(\{1,3\}\;\;\{2,3\}\bigr)\;\bigl(\{1,4\}\;\;\{2,4\}\bigr)\;\bigl(\{3,4\}\bigr).
$$
If $\sigma = (1\;2\;3)$, then $\sigma_E$ has two cycles:
$$
\sigma_E \;=\; \bigl(\{1,2\}\;\;\{2,3\}\;\;\{1,3\}\bigr)\;\bigl(\{1,4\}\;\;\{2,4\}\;\;\{3,4\}\bigr).
$$
If $\sigma = (1\;2\;3\;4)$, then $\sigma_E$ has two cycles:
$$
\sigma_E \;=\; \bigl(\{1,2\}\;\;\{2,3\}\;\;\{3,4\}\;\;\{1,4\}\bigr)\;\bigl(\{1,3\}\;\;\{2,4\}\bigr).
$$
Finally, if $\sigma=(1\;2)(3\;4)$, then $\sigma_E$ has four cycles:
$$
\sigma_E \;=\; \bigl(\{1,2\}\bigr)\;\bigl(\{3,4\}\bigr)\;\bigl(\{1,3\}\;\;\{2,4\}\bigr)\;\bigl(\{1,4\}\;\;\{2,3\}\bigr).
$$
Thus, the number of isomorphism classes of graphs with $4$ vertices is
$$
\frac{1}{|S_n|}\sum_{\sigma\in S_n} 2^{N(\sigma_E)} \;=\; \frac{2^6 + 6(2^4) + 8(2^2) + 6(2^2)+3(2^4)}{24} \;=\; 11.
$$
Wikipedia has a nice picture of these eleven classes:

Improvement: Actually, it's not too hard to find a general formula for $N(\sigma_E)$.  In particular:


*

*Each $k$-cycle of $\sigma$ gives rise to $\lfloor k/2\rfloor$ orbits of edges between vertices of the $k$-cycle, and

*Each $\{j$-cycle, $k$-cycle$\}$ pair gives rise to $\gcd(j,k)$ orbits of edges between vertices in the two cycles.
Thus, if $\sigma$ has cycles of length $k_1,\ldots,k_m$ (including cycles of length $1$), then
$$
N(\sigma_E) \;=\; \sum_{i=1}^m \left\lfloor\frac{k_i}{2}\right\rfloor \,+\, \sum_{i<j} \gcd(k_i,k_j).
$$
For example, if $\sigma$ is the product of $6$-cycle, a $4$-cycle, and a $1$-cycle, then
$$
N(\sigma_E) \;=\; \left\lfloor\frac{6}{2}\right\rfloor + \left\lfloor\frac{4}{2}\right\rfloor + \left\lfloor\frac{1}{2}\right\rfloor + \gcd(6,4) + \gcd(6,1) + \gcd(4,1) \;=\; 9.
$$
Example: Let's compute the number of isomorphim classes of graphs with $5$ vertices.  Here are the possible cycle structures for elements of $S_5$:


*

*$\sigma=(*)(*)(*)(*)(*)$, $1$ element, $N(\sigma_E) = 10$

*$\sigma=(*\;*)(*)(*)(*)$, $10$ elements, $N(\sigma_E) = 7$

*$\sigma=(*\;*\;*)(*)(*)$, $20$ elements, $N(\sigma_E) = 4$

*$\sigma=(*\;*\;*\;*)(*)$, $30$ elements, $N(\sigma_E) = 3$

*$\sigma = (*\;*\;*\;*\;*)$, $24$ elements, $N(\sigma_E) = 2$

*$\sigma = (*\;*)(*\;*)(*)$, $15$ elements, $N(\sigma_E) = 6$

*$\sigma = (*\;*\;*)(*\;*)$, $20$ elements, $N(\sigma_E) = 3$


Thus, the number of isomorphism types of graphs with five vertices is:
$$
\frac{1(2^{10}) + 10(2^7) + 20(2^4) + 30(2^3) + 24(2^2) + 15(2^6) + 20(2^3)}{120} \;=\; 34.
$$
