Number of distinct digraphs with 3 edges?

Question

I asked a question like this a while ago but I don't think I worded it very well so here is a second attempt.

I am trying to find a systematic way of finding all distinct possible ways a digraph can be created with 3 edges. Loops count as an edge. By distinct, I mean that no digraph can be turned into another by flipping, rotating, or re-labeling the vertices.

I am trying to do these for 3,4,...,n number of edges so I am trying to find a more systematic way of doing so. Any advice is appreciated. Thank you for reading.

Answer 1

If you fix $n$ vertices and $k$ edges, you can form $\binom{n^2}{k}$ digraphs (with loops). The complete graph has exactly $n^2$ edges; we have free and independent choice where edges begin and where they end, including beginning and ending with the same vertex. Each such digraph represents an unordered selection of $k$ of these $n^2$ vertices.

Answer 2

If the answer for 2 edges is 11, then I believe I found this in the On-Line Encyclopedia of Integer Sequences and the number for 3 edges is 52.

Here are the 11 digraphs for 2 edges:

1. $A \rightarrow^2 A$ (by which I mean there are two loops on $A$)
2. $A \rightarrow A$ and $A \rightarrow B$
3. $A \rightarrow A$ and $B \rightarrow B$
4. $A \rightarrow^2 B$
5. $A \rightarrow B$ and $B \rightarrow A$
6. $A \rightarrow B$ and $B \rightarrow B$
7. $A \rightarrow A$ and $B \rightarrow C$
8. $A \rightarrow B$ and $A \rightarrow C$
9. $A \rightarrow B$ and $B \rightarrow C$
10. $A \rightarrow B$ and $C \rightarrow B$
11. $A \rightarrow B$ and $C \rightarrow D$

The sequence A052171 begins 1, 2, 11, 52, 296. You might also benefit from looking at the related A138107 which includes some PARI code.

If the 11 possibilities above includes some loop/edge configurations you do not want, then please specify what types you mean to allow.

---

OK, so you don't want to count repeated edges. Then I think the count for three edges is 32.

My reasoning is to use the 52 from A052171 and subtract the ones that have repeated edges. Removing the repeated edge would leave a graph with two edges (possibly repeated), which is exactly the list of 11 above. Going the other direction, how many ways can we repeat an edge in those 11 graphs to make a 3 edge digraph with a repeated edge? For #1 the only possibility is $A \rightarrow^3 A$, same for #4. For #2 there are two possibilities: $A \rightarrow^2 A$ and $A \rightarrow B$, and also $A \rightarrow A$ and $A \rightarrow^2 B$. That's the same situation for #3 and #5-#11. That builds 20 three edge graphs with repeated edges (I don't think there's any overcounting), then $52-20 = 32$.

I don't see an OEIS sequence for this situation (not surprising as conditions get more specialized). You could continue to work from A052171, i.e., for four edges the count is 296 minus the number with any repeated edge, but counting the digraphs with repeated edges will get trickier.