Number of directed graphs Hi i have to find the number of directed graphs with vertices labelled {${1... n}$}
My idea: For each vertex we can put $n$ ($n-1$ other vertices $+1$ itself) possible edges. So it would be something like $n*2^n$ possible directed graphs.
Is my idea correct. How can i improve it ?
 A: A directed graph can be viewed as a relation. Given a fixed vertex set, the edge set $E \subset [n] \times [n]$, where $[n] = \{1, \ldots, n\}$. The possible subsets of $[n] \times [n]$ are contained contained in the power set $2^{[n] \times [n]}$. So there are $2^{n^{2}}$ possible directed graphs.
Note: My solution allows for loops. If you exclude loops, then you are looking at subsets of $([n] \times [n]) \setminus \{ (i, i) : i \in [n] \}$, which has cardinality $n^{2} - n$. So without loops, there would be $2^{n^{2}-n}$ possible digraphs.
Edit: A small critique of your solution. Each vertex has $2^{n}$ possible edges incident to it. You are determining the digraph by the neighborhood of each vertex. So you have:
$$N(v_{1}) \cup N(v_{2}) \cup \ldots \cup N(v_{n})$$
Where $N(v_{i}) \cap N(v_{j}) = \emptyset$ for distinct $i, j$. For each $i \in [n]$, $N(v_{i}) \in 2^{[n]}$, so there are $2^{n}$ possible options for each $v_{i}$. Hence, there are $(2^{n})^{n} = 2^{n^{2}}$ possible digraphs.
A: For every pair $u,v\;$of vertices, there's either 


*

*Only an edge from $u\;$to $v$.$\\[4pt]$

*Only an edge from $v\;$to $u$.$\\[4pt]$

*Both.$\\[4pt]$

*Neither.


So $4$ choices for each pair of vertices.

Since there are $\binom{n}{2}$ pairs of vertices, there are 
$$4^{\binom{n}{2}} = 2^{n^2-n}$$
 directed graphs on a given set of $n$ vertices.

I'm assuming no multiple edges with the same source and target, and no loops.

If loops are allowed, then for each loopless directed graph, there are $2^n$ ways of defining loops (since each of the $2^n$ subsets of the set of $n$ vertices could be the subset having loops). Thus, the new count would be
$$(2^n)\bigl(2^{n^2-n}\bigr)=2^{n^2}$$
As regards your error . . .

As you noted, allowing loops, each vertex has $2^n$ choices for edges originating from that vertex.

Since there are $n$ vertices, the multiplication rule yields a count of $(2^n)^n = 2^{n^2}\!\!,\;$not $n2^n$.

In other words, there should be $n\;$factors, each equal to $2^n,\;$rather than $n$ summands, each equal to $2^n$.
A: I understand that for every ordered pair of vertices $(x,y)$ ($x$ and $y$ may be equal or different) there can be, or not be, an arrow from $x$ to $y$.
Then, there are $n^2$ possible arrows. The number of graphs is, hence, the number of subsets of the set of all possible arrows, that is, $2^{n^2}$.
