The problem is as follows. Given a set $V$ of $n$ vertices, and an empty set of edges $E$, for every possible edge $(u,v)$ in the graph, choose to include add it to $E$ with probability $1/2$. What is the probability that the final product is a tree?
I'm going in circles on this one, having no idea where to start. Here's my thinking so far: I know we'll need to choose exactly $(n-1)$ edges, and there are a total of $\binom{n}{2}$ possible edges. This means you need to choose to include an edge $(n-1)$ times out of $\binom{n}{2}$ times, and since there are a total of $2^\binom{n}{2}$ possible sequences of choices, the probability of choosing exactly $n-1$ edges is $\binom{\binom{n}{2}}{n-1} / 2^{\binom{n}{2}}.$ However, not all of these will be trees. By Cayley's theorem there are $n^{n-2}$ total trees on $n$ vertices, but I don't know how to calculate how many general graphs (i.e. including disconnected graphs) there are with $n$ vertices and $n-1$ edges. So I'm not sure how to formulate this. And perhaps I'm overlooking a much simpler way to calculate these. Help!!