Is there a theorum or algorithm for counting the number of disjoint combinations of sets of sets with a time complexity better than $O(n^k)$?
Given $f(\mathbf{S},k)$ is the function to count the disjoint combinations of sets of size $2$ taken in groups of $k$,
where $1 \le k \le 8$, from a set of sets, $\mathbf{S}$, with a size $n$, where $k \le n \le 1000$.
Example set:
$$\mathbf{S} = \{\{0,1\},\{0,2\},\{1,2\},\{1,3\},\{2,3\},\{4,5\}\}$$
Expected values:
$$f(\mathbf{S},1) = 6\,|\,\mathbf{S}$$
$$f(\mathbf{S},2) = 7\,| \left\{\begin{gather}
\{0,1\},\{2,3\} \\
\{0,1\},\{4,5\} \\
\{0,2\},\{1,3\} \\
\{0,2\},\{4,5\} \\
\{1,2\},\{4,5\} \\
\{1,3\},\{4,5\} \\
\{2,3\},\{4,5\}
\end{gather}\right\}$$
$$f(\mathbf{S},3) = 2\,| \left\{\begin{gather}
\{0,1\},\{2,3\},\{4,5\} \\
\{0,2\},\{1,3\},\{4,5\}
\end{gather}\right\}$$
$$f(\mathbf{S},4..8) = 0\,|\,\emptyset$$
If all elements of $\mathbf{S}$ are disjoint then the function achieves a maximum value, $f_m(\mathbf{S},k)$, expressed as consecutive sums of sums, algebraic notation, or combination/choose notation:
$$f_m(\mathbf{S},1) = \sum_{a=1}^{n-k+1}{1}=n={{n}\choose{1}}$$
$$f_m(\mathbf{S},2) = \sum_{a=1}^{n-k+1}{\sum_{b=1}^{a}{1}}=\cfrac{1}{2}(n^2 - n)={{n}\choose{2}}$$
$$f_m(\mathbf{S},3) = \sum_{a=1}^{n-k+1}{\sum_{b=1}^{a}{\sum_{c=1}^{b}{1}}}=\cfrac{1}{6}(n^3-3n^2+2n)={{n}\choose{3}}$$
$$f_m(\mathbf{S},4) = \sum_{a=1}^{n-k+1}{\sum_{b=1}^{a}{\sum_{c=1}^{b}{\sum_{d=1}^{c}{1}}}}=\cfrac{1}{24}(n^4-6n^3+11n^2-6n)={{n}\choose{4}}$$
$$f_m(\mathbf{S},5) =\,...\,=\cfrac{1}{120}(n^5-10n^4+35n^3-50n^2+24n)={{n}\choose{5}}$$
$$f_m(\mathbf{S},6) =\,...\,=\cfrac{1}{720}(n^6-15n^5+85n^4-225n^3+274n^2-120n)={{n}\choose{6}}$$
$$f_m(\mathbf{S},7) =\,...\,=\,...\,= {{n}\choose{7}}$$
$$f_m(\mathbf{S},8) =\,...\,=\,...\,= {{n}\choose{8}}$$
Note that this also represents the function to count both the disjoint and intersecting combinations which could be useful if there is
only a theorum or algorithm for counting intersecting combinations.
Example pseudo-code to compute (for $k = 3$):
$$
f(\mathbf{S}_{1..n},3) = a\forall\{3..n\},b\forall\{2..a-1\},c\forall\{1..b-1\}, \mathbf{S}_a \cap \mathbf{S}_b \cap \mathbf{S}_c = \emptyset
$$
However, the time complexity of running the algorithm is too high: $O(n^k)$
I am looking for a better time complexity algorithm to compute the count of disjoint combinations; preferably no worse than $O(n^2)$.
I am having trouble finding any set or combinatorics topics addressing this specific problem.
Revisions based on Ipsil's answer: I see that if I generate a graph of elements and connect edges between disjoint sets then I could use the $n$-clique problem to solve this but it would still be NP-complete.
But what if I arranged the subset elements into digrpahs: Disjoint digraphs A and B
If I define a new function $g(\mathbf{G},k)$ to count the combinations of taking $k$ node-edge-nodes from graph $\mathbf{G}$ then I can compute the original answer:
$$g(A,1) = 5\,|\,\text{Number of edges}$$
$$g(A,2) = 2\,|\,\left\{\begin{gather}
\{0-1, 2-3\} \\
\{0-3, 1-2\}
\end{gather}\right\}$$
$$g(B,1) = 1$$
$$g(B,2) = 0\,|\,\emptyset$$
$$f(\mathbf{S},1) = g(A,1) + g(B,1) = 5 + 1 = 6$$
$$f(\mathbf{S},2) = g(A,1) * g(B,1) + g(A,2) + g(B,2) = 5 * 1 + 2 + 0 = 7$$
$$f(\mathbf{S},3) = g(A,2) + g(B,2) = 2 + 0 = 2$$
$$...$$
So is there a graph theory algorithm for counting 2-element subgraphs of a digraph taken $k$ at a time?
Well, let's look at a rearrangement of your problem. Take a set of sets, as you have above, and represent each element of that set of sets as a vertex for a graph. From there, connect (undirected) each set vertex such that their intersection is empty. An example, as done to your original set:
(Apologies for the terrible drawing skills)
With your problem constructed in this format, counting all of $n$ mutually disjoint pairs is finding all cliques of size $n$; this is an NP-complete problem, which you can read more about here.