combinatoricsgraph theory
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 ?
The case where vertices are labeled would be easy to count. The tool that lets us go from labeled to unlabeled vertices is the Pólya enumeration theorem. (The Wikipedia article gives an example of using this to count undirected graphs with a fixed number of edges, and the directed case is only slightly different.)
I will forget about isolated vertices for now, and allow directed edges $vw$ and $wv$ to coexist. So let's start with the complete directed graph (with $n$ vertices and all $N := n(n-1)$ possible directed edges), and color the edges with two colors: a color that represents "there is an edge" (with weight $1$) and a color that represents "there is no edge" (with weight $0$). The generating function of the set of colors is $f(t) = 1+t$. The weight of a coloring is the total weight of the colors used, so it's the number of edges in our graph; therefore, we want to find the number of colorings with a fixed weight.
We take $G$ to be the group $S_n$ acting on the vertices of the complete directed graph. To apply the Pólya enumeration theorem as in the Wikipedia article, we need to compute $Z_G(t_1, t_2, \dots, t_N)$. So, for each permutation $\sigma$ of the vertices and each $k \in \{1, \dots, N\}$, we need to compute $c_k(\sigma)$, the number of $k$-cycles in the action of $\sigma$ on the set of edges.
For example, let's try this for $n=3$ vertices, with $N = 6$ possible edges. Here, there are $3$ types of permutations:
So we get $Z_G(t_1, t_2, t_3, t_4, t_5, t_6) = \frac16(t_1^6 + 3 t_2^3 + 2 t_3^2).$ We might as well make this $Z_G(t_1, t_2, t_3)$ since no longer cycles appear.
By the Pólya enumeration theorem, the generating function of directed graphs on $3$ vertices up to isomorphism is \begin{align} Z_G(1 + t, 1 + t^2, 1 + t^3) &= \frac16((1+t)^6 + 3(1+t^2)^3 + 2(1+t^3)^2) \\ &= 1 + t + 4 t^2 + 4 t^3 + 4 t^4 + t^5 + t^6 \end{align} so there are $1, 1, 4, 4, 4, 1, 1$ directed graphs on $3$ vertices with $0, 1, 2, 3, 4, 5, 6$ edges respectively. Here is a diagram of all these graphs to verify the count:
You also wanted to rule out isolated vertices, which this doesn't do, but that's easy to fix. Let's say that $a_{n,m}$ is the number of $n$-vertex $m$-edge digraphs without the isolated vertex condition, and $a_{n,m}^*$ is the number that have no isolated vertices. Then we have $$ a_{n,m} = a_{0,m}^* + a_{1,m}^* + a_{2,m}^* + \dots + a_{n,m}^* $$ because the number of $n$-vertex $m$-edge digraphs with $k$ isolated vertices is counted by $a_{n-k,m}^*$. From this, we can get $a_{n,m}^* = a_{n,m} - a_{n-1,m}$.
There are $\binom{V}{2}=V(V-1)/2$ distincy pairs of vertices. For any pair of vertices $\{u,v\}$, any one of the 3 options can hold:
Hence total number of directed graphs on $V$ vertices is $3^{V(V-1)/2}$.
Best Answer
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.