How many connected, simple graphs are on n vertices I'm trying to find a formula that will give me the number of connected, simple graphs on n vertices, not taking in consideration isomorphism.
I though that it can be done by taking the difference between the total number of possible graphs and disconnected graphs.
We will have :
$2^{\binom{n}{2}}$ , where $\binom{n}{2}$ will determine the number of possible edges(this will give us total number of possible graphs)
The disconnected graphs will consist of $n-2, n-3 ...$ edges(since $n-1$ is a tree). The number of disconnected graphs will depend on number of vertices, so I though it would be equal to $\sum_{i=2}^{n-1}(2^{\binom{n}{2} -i})$.
Altogether : $2^{\binom{n}{2}}-\sum_{i=2}^{n-1}(2^{\binom{n}{2} -i})$ . And I'm stuck here. What would be a correct approach to this problem?
 A: We will reduce the problem of counting the number of labeled simple graphs on $n$ vertices to enumerating partitions of $n$. Our main strategy is to use Mobius inversion on the partition lattice. 
Let $G=(V,E)$ be a graph on $n$ vertices. For any subgraph $G'=(V,E')$, where $E'\subseteq E$, we denote $C_{G'}$ to be the partition of vertices corresponding to the connected components of $G'$. We now define $g: \Pi_n \to \mathbb{Z}$ and $f: \Pi_n \to \mathbb{Z}$ as follows. Let $g(B)$ be the number of simple subgraphs $G'=(V,E')$ such that $C_{G'}=B$, and let $f(B)$ be the number of simple subgraphs $G'=(V,E')$ such that $C_{G'}\le B$. Then 
$$ f(B)= \sum_{A\le B} g(A) $$
We call a partition of $n$ to be type $(k_1,k_2,\dots,k_n)$ if the partition contains $k_i$ blocks of size $i$. Now if $B\in \Pi_n$ has type $(k_1,k_2,\dots,k_n)$, then 
$$ f(B)= 2^{\sum_{i=2}^n k\dbinom{i}{2}}$$
By Mobius Inversion, we have 
$$ g(\widehat{1})=\sum_{A\le B}\mu_{\Pi_n}(A,\widehat{1})f(A)$$
Let $\sum_{i=1}^n k_i=k$. Then $|A|=k$, and $[A,\widehat{1}]\cong \Pi_k$. Hence $$\mu_{\Pi_n}(A,\widehat{1})=\mu_{\Pi_k}(\widehat{0},\widehat{1})=(-1)^{k-1}(k-1)!$$ Note that there are 
$$ \frac{n!}{\prod_{i=1}^n k_i!i!^{k_i}}$$
partitions of $n$ of type $(k_1,k_2,\dots,k_n)$. Thus the number of labeled simple graphs on $n$ vertices is
$$ g(\widehat{1})=\sum_{\substack{(k_1,k_2,\dots,k_n) \\ \sum_{i=1}^n ik_i=n}} \left[2^{\sum_{i=2}^n k\dbinom{i}{2}}\right]\left[(-1)^{-1+\sum_{i=1}^n k_i}\right]\left(-1+\sum_{i=1}^n k_i\right)!\left(\frac{n!}{\prod_{i=1}^n k_i!i!^{k_i}}\right)  $$
