Counting sets by their connectedness
Solution 1:
New Notations: Always fix $r$. Suppose $L=(c_1, c_2, \ldots, c_l)$ is a list of non-decreasing natural numbers. Denote by $|L|$ ($=l$) the length of the list and $\sum L = c_1 + \ldots + c_l$ the sum of entries in $L$. Let $T(n, L)$ count the number of sets $U = \{u_1, \ldots, u_{m}\}$, where $m=\sum L$, each $u_i$ is an $r$-subset of $[n]$ and $\cup U = [n]$, whose intersection graph have exactly $l$ connected components with sizes $c_1, c_2, \ldots, c_l$.
Relation with the Old Notation: $$T_{n,m}(c)=\sum_{|L| = c, \sum{L}=m}T(n, L).$$
Inductive Property:
- If $L = L_1+L_2$ (list concatenation) such that $L_1 < L_2$ (i.e., all entries in $L_1$ is less than the ones in $L_2$), then $$T(n,L)=\sum_{n_1+n_2=n} {n\choose n_1} T(n_1, L_1)T(n_2, L_2).$$
- Suppose $L = (c,c,\ldots, c) =: (c)^l$, where $l=|L|$. We have $$T(n, L)=\sum_k\sum_{l_1 + \ldots + l_k = l}\frac{1}{l_1!\ldots l_k!}\sum_{\ n_1 < \ldots < n_k}\frac{n!}{(n_1!)^{l_1}\ldots(n_k!)^{l_k}}1_{l_1n_1 + \ldots + l_kn_k=n}T(n_1, (c))^{l_1}\ldots T(n_k, (c))^{l_k}.$$
Boundary Condition: $T(n, L)=0$ if $n < r$ or $n > r|L|$.
Restriction Formula: Note that the total number of sets $U = \{u_1, \ldots, u_m\}$ each $u_i$ is an $r$-subset of $[n]$ is equal to $${{n\choose r}\choose m}.$$ On the other hand, one can count it using $T_{n,m}(c)$ according to $\cup U$. We get the total number of $U$ is equal to $$\sum_{n_0\leq n}{n\choose n_0}\sum_cT_{n_0, m}(c) = \sum_{n_0\leq n}{n\choose n_0}\sum_l\sum_{|L| = l, \sum{L}=m}T(n_0, L).$$ Therefore we have $$\sum_{n_0\leq n}{n\choose n_0}\sum_l\sum_{|L| = l, \sum{L}=m}T(n_0, L) = {{n\choose r}\choose m}.$$ We rewrite it as $$T(n,(m)) = {{n\choose r}\choose m} - \sum_{n_0 < n}{n\choose n_0}\sum_l\sum_{|L| = l, \sum{L}=m}T(n_0, L) - \sum_{l>1}\sum_{|L| = l, \sum{L}=m}T(n, L)$$
Punch Line: Define $(n_0, L_0) < (n, L)$ if $n_0 < n$ or $n_0 = n$ but $|L_0| > |L|$. Clearly, one can use the inductive properties, the boundary condition and the restriction formula to compute $T(n,L)$ once $T(n_0,L_0)$ are given for all $(n_0, L_0)< (n,L)$ (call $(n,L)$ complexity of $T(n,L)$) since in all formulas involved the complexity on the right hand side is always less than the complexity on the left hand side.
Update: For computational reasons (as OP mentioned in the comment), one may want to replace the inductive property 2 by a simpler recursion $$T(n,(c)^l)=\sum_{k}{n-1\choose k-1}T(k,(c))T(n-k,(c)^{l-1}).$$ Again the idea in the inductive properties is indeed based on OP's answer.
Solution 2:
I recently came up with a faster solution to this problem that reduces the recurrence dimension by 1.
Let $T_r(n, m, c)$ represent the number we are looking for, ie. the number of ways to take $m$ subsets of $[n]$ such that each subset has size $r$, the subsets cover $[n]$, and their intersection graph has $c$ connected components. I made $r$ a subscript because it is held fixed throughout. The logic is similar to $T_n^{c \times \ell}$ in my answer above. Consider the connected component that covers the element "1" from the ground set. Suppose it consists of $s$ subsets and that it covers $k$ total elements. There are $\binom{n - 1}{k - 1}$ ways to choose the covered elements which leads to the recurrence for $c > 1$.
$$T_r(n, m, c) = \sum_{k} \sum_{s} \binom{n - 1}{k - 1} \; T_r(n\!-\!k, \,m\!-\!s,\,c\!-\!1) \; T_r(k, s, 1) $$
For connected graphs $c = 1$ we get the same restriction formula from before: all the possible graphs given $m$ minus those that don't cover $[n]$ minus those that have more than 1 connected component.
$$ T_r(n, m, 1) \; = \; {{n \choose r} \choose m} \; - \; \sum_{k \, < \, n} \sum_{c} {n \choose k} T_r(k, m, c) \; - \; \sum_{c \, > \, 1} T_r(n, m, c)$$