A digraph is a graph where every edge is directed. How many digraphs on $n$ vertices are there? So far I have that between any two vertices (say $j$ and $k$) there are 3 options.


*

*there is no edge between $j$ and $k$

*there is an edge directed from $j$ to $k$

*there is an edge directed from $k$ to $j$


And so from this, we can see that there must be $3^{\binom{n}{2}}$ digraphs on $n$ vertices. 
I'm not sure if it should be $\binom{n}{2}$ or $\binom{n}{3}$? Can anybody clarify this for me?
 A: In a directed graph, there are $n(n-1)$ distinct edges, each of these can be present or not. Thus the number of digraphs with $n$ vertices should be
$$2^{n(n-1)}$$
Note that this allows two vertices to be connected by directed edges in both ways. This coincides with the definition on wikipedia (see the example image).
If instead you want to probhibit situations like $v\leftrightarrow v'$ (double-connectedness), you are correct in your enumeration, we pick two vertices in $\binom n2$ ways and assign one of three cases to it independently of the others:
$$3^{\binom n2} = 3^{\frac12 n(n-1)}$$
If the same method was used do allow the fourth case, we would get the original result:
$$4^{\binom n2} = (2^2)^{\frac12 n(n-1)} = 2^{n(n-1)}$$
A: As ever in combinatorics, you need to be crystal clear about what you're counting, and in particular about equivalence classes.
The OEIS sequence A000273: Number of directed graphs (or digraphs) with n nodes counts equivalence classes up to graph isomorphism and appears to exclude graphs with cycles of length 1 (as otherwise there would be two graphs on one vertex).
From your description you seem to be counting digraphs on $n$ labelled vertices without cycles of length 1 or 2.
So $3^\binom{n}{2}$ could be correct or not depending on what precisely the question is. $3^\binom{n}{3}$ is definitely not correct.
