How to determine the number of directed/undirected graphs? I'm kind of stuck on this homework problem, could anyone give me a springboard for it? If we have $n\in\mathbb{Z}^+$, and we let the set of vertices $V$ be a set of size $n$, how can we determine the number of directed graphs/undirected graphs/graphs with loops etc.? Is there a formula for this? I feel like it can be done using combinatorics but I can't quite figure it out. Any ideas?
Thanks!
 A: A start: We will show how to count labelled, loopless, undirected graphs. There are $\binom{n}{2}$ ways to choose a set $\{u,v\}$ of two vertices. For every such set, we say yes or no depending on whether we have decided to join $u$ and $v$ by an edge.  Alternately, but somewhat less concretely, let $P$ be the set of all (unordered) pairs. This set $P$ has cardinality $\binom{n}{2}$. To specify a loopless undirected graph, we choose a subset of $P$ and connect any unordered pair in that subset by an edge. How many subsets does $P$ have?
To extend to graphs with possible loops (but at most one per vertex) there is a similar yes/no process. 
A: For labeled vertices:
To count undirected loopless graphs with no repeated edges, first count possible edges. As Andre counts, there are $\binom{n}{2}$ such edges. One by one, each edge is either included or excluded. So this gives $2^{\binom{n}{2}}$ possible graphs.
If loopless graphs with no repeated edges are directed, each pair of vertices $a<b$ provides $3$ possibilities for a (potentially absent) edge. Do you see what they are and how that modifies the count?
If there are loops (but still no repeated edges), then either of the above scenarios are modified by realizing that there are $n$ more pairs of points to consider - the ones where $a=b$. Do you see how this would modify the count of graphs? Watch out - it doesn't really make sense to count a loop as directed.
A: Without some restrictions, there are infinitely many, so I suspect you at least have the assumption that you can't have more than one edge between a single pair of vertices.
You should think about what the maximal number of possible edges you could have is in a graph with $n$ vertices (this is why we should assume no multiple edges, so the number is finite, but it will be different depending on whether you allow loops or not). Then to specify a particular graph on $n$ vertices, you need to specify whether each of the possible edges appears in your particular graph or not. If your graph should be oriented, you then have the additional choice of which way the edge should point. You should then be able to ennumerate the total number of possible choices (if you can't, let me know and I'll add more detail here - as this is tagged homework I don't want to give too much away immediately!).
