How many sets correspond to connected graphs I'm trying to solve this project euler problem.  I don't want to get too much help, since that would defeat the purpose, but I'm hitting a wall, so I'm asking a related problem here, from which I'll hopefully be able to work toward a solution.  Let $X \subseteq (\mathcal P(\{1,\ldots,n\})-\emptyset)
$ such that every element of $\{1,\ldots,n\}$ is a member of at least one element of $X$, that is $\bigcup_{s \in X} s = \{1,\ldots,n\}
$. Let $G(X)$ be the graph whose vertices are elements of $X$ and whose edges connect vertices with non-empty intersections.  I'm looking for some way to calculate the number of possible $X$ such that $G(X)$ is connected, or failing that some insight into how else I might approach the problem.
 A: NB This isn't a full answer, but it gives an alternative perspective which may be useful.
I find it a bit easier to follow with fewer levels of indirection:
$$X \subseteq (\mathcal P(\{1,\ldots,n\})-\emptyset)$$
with the additional constraint $$\bigcup_{s \in X} s = \{1,\ldots,n\}$$
Consider the graph $H$ whose vertices are $\{1,\ldots,n\}$ and whose edges form all two-element subsets of the elements of $X$. In other words, every set $s \in X$ is a clique in $H$. If two elements $s_1, s_2 \in X$ have an element in common, all of the elements of $s_1 \cup s_2$ are in the same connected component of $H$. Therefore $H$ has exactly as many connected components as $G$.
For any given $H$, the cliques form an upper bound on $X$. The question of which subsets of the cliques are strictly necessary to generate $H$ is not obviously trivial. However, since your question asks about the case where $G$ (and hence $H$) is connected: each spanning tree corresponds to an $X$ consisting of $n-1$ two-element sets; and each $X$ which gives a connected $G$ can be extended by adding new sets or by adding elements to the existing sets. An inclusion-exclusion calculation might be feasible.
