How many sets correspond to connected graphs

Question

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.

Answer 1

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.