How many are non isomorphic tournaments (directed clique) with $n=5$ vertices?
I'm not sure how to understand isomorphism here. This problem was in the set of problems on Burnside's lemma but it's different than the rest, I think. Normally I was asked to count the number of significantly different colorings of necklace or chessboard which was very nice and the group for Burnside's lemma was given explicit – simply all rotations. But here I don't know what is the group, how to approach this.
Is it very difficult to solve this in general – for $n\in\mathbb{N}$?
Will it be useful here the term: graph automorphism? How to understand it? Because I have it in the next problem.
Best Answer
Judging from the question, a lot of the confusion is converting from group actions terminology to graph theory terminology. I'll try to clarify.
Let $\mathcal{A}$ be the set of labelled tournaments on the vertex set $\{1,2,\ldots,5\}$. We know $$|\mathcal{A}|=2^{{5 \choose 2}}=1024$$ since each edge can go in one of two directions. The symmetric group $S_5$ acts on $\mathcal{A}$ by permuting the vertex labels.
Pick an arbitrary tournament $T \in \mathcal{A}$ and an arbitrary permutation $\alpha \in S_5$.
We say that $T$ and $\alpha(T)$ are isomorphic (which we intuitively interpret as meaning structurally equivalent).
We can define an equivalence relation on the set of $5$-vertex tournaments, with tournaments $A$ and $B$ being equivalent if $\alpha(A)=B$ for some $\alpha \in S_5$. The equivalence classes are called isomorphism classes or orbits. The number of non-isomorphic tournaments, is the number of orbits.
Burnside's Lemma gives a formula the number of orbits under a group action. However, to use it, we need to find a way of counting the number of tournaments $T$ that are "fixed" by each $\alpha \in S_5$.
Thus, to use Burnside's Lemma, for each $\alpha \in S_5$, we need to find the size of $$F_\alpha:=\{T \in \mathcal{A}:\alpha(T)=T\}$$ which gives the number of orbits (the number of non-isomorphic tournaments) as: $$\frac{1}{|S_5|} \sum_{\alpha \in S_5} |F_\alpha|.$$
This might sound horrid (since $|S_5|=120$), but it's made much easier by the observation that $|F_\alpha|$ varies only with the cycle structure of $\alpha$.
The possible cycle structures are:
For each of these cycle structures, e.g. (2,2,1), we can pick a representative, e.g. $\beta=(12)(34)(5)$, and find $|F_\beta|$.
Hint: The number of permutations with a given cycle structure is given here, for example.
Hint: Automorphisms of tournaments must have odd order. (Why?) This means we need only consider the cycle structures $(1,1,1,1,1)$, $(3,1,1)$ and $(5)$.
Thus, the question is really asking for $|F_{(1)(2)(3)(4)(5)}|=1024$, $|F_{(123)(4)(5)}|$ and $|F_{(12345)}|$.