Find number of full connected directed graphs where $|V|=5$ (directed $K_5$)
solution
According to OEIS there are $42$ graphs like that.
Let say that we have graph $G$ and we want to find how many there are graphs which are non isomorphic to it and has the same build (I mean directions of edges between given nodes).
I want to use Polya theorem. We have $5$ rotations due to normal rotate and $2$ rotation due to mirror reflection. So we can treat that as operation with group
$$ \mathbb Z_2 \times \mathbb Z_5 \mbox{ a it has $10$ elements } $$
Ok. So let look at cycles:
- identity - $5$ cycles of size $1$: $x_1^5$
- rotate one right - $1$ cycle of size $5$: $x_5$
- rotate two right - $1$ cycle of size $5$: $x_5$
- rotate four right - $1$ cycle of size $5$: $x_5$
- rotate five right - $1$ cycle of size $5$: $x_5$
and the same system when we do mirror reflection
Ok so our cyclic index is $$I(x_1,x_2,x_3,x_4,x_5) = \frac{2}{10}(x_1^5 + 4x_5) = \frac{1}{5}(x_1^5 + 4x_5) $$
I want to use $1$ color so $I(1,1,1,1,1) = 1$. So for given system of direction I have exactly $1$ non isomorphic graph. It means that only what we have to do is count all combinations of directions. So result is $$ 2^{\binom{5}{2}} = 2^{10} = 1024 \neq 42$$
Where I failed...?
I don’t know the term “full connected directed graph” that you used. I take it that by “complete digraphs” the OEIS sequence refers to digraphs that have at least one directed edge between each pair of vertices, and this is equal to the number of “oriented graphs (i.e., digraphs with no bidirected edges)” because it doesn’t matter whether you allow $0$ or $1$ directed edges per pair or $1$ or $2$ directed edges per pair. Since I find it easier to think and write about, I’ll allow $0$ or $1$ directed edges per pair.
A lot has already been discussed in the comments. Let’s go through the seven conjagcy classes of $S_5$.
The identity fixes all labelled graphs, of which there are $3^{10}$, since we have $3$ options for each pair of vertices: An edge in one of two directions, or no edge.
In a fixed point of a $2$-cycle (of which there are $10$), the two vertices in the cycle can’t be connected, and all their connections to the other $3$ vertices must be the same, which leaves $3^6$ choices.
In a fixed point of a $3$-cycle (of which there are $20$), the vertices in the cycle must be either not connected or cyclically connected in one of two orientations, which makes $3$ options. Their connections to the other $2$ vertices must all be the same. That leaves $3^4$ options.
In a fixed point of a $4$-cycle (of which there are $30$), the vertices in the cycle must be either not connected or cyclically connected, and their connections to the remaining vertex must be the same. That leaves $3^2$ options.
In a fixed point of a $5$-cycle (of which there are $24$), all the vertices must be either not connected or cyclically connected. That leaves $3^1$ options.
In a fixed point of a permutation with two $2$-cycles (of which there are $15$), the pair in each cycle must not be connected, their connections with the remaining vertex must be pairwise the same and their connections among themselves must be pairwise the same. That leaves $3^4$ options.
And in a fixed point of a permutation with one $2$-cycle and one $3$-cycle (of which there are $20$), the $2$-cycle must not be connected, the $3$-cycle must be either not connected or cyclically connected, and the connections between the cycles must all be the same because they all form a single orbit (these permutations have order $6$). That leaves $3^2$ options.
Thus, the number of equivalence classes of oriented graphs on $5$ unlabelled vertices under isomorphism is
$$ \frac1{5!}\left(3^{10}+10\cdot3^6+20\cdot3^4+30\cdot3^2+24\cdot3^2+15\cdot3^4+20\cdot3^2\right)=582\;, $$
as given in the OEIS sequence.