# Thread: Counting subsets of disjoint sets

1. ## Counting subsets of disjoint sets

The set, $A$, contains numbers: $\{1,2,\text{...},n\}$.
The set, $B$, contains any subset of $A$ with cardinality $2$: $\{\{1,2\},\{1,3\},\text{...},\{n-1,n\}\}$
$C_1,C_2,C_3$ are some pairwise disjoint sets that satisfy $C_1\cup C_2\cup C_3=B$.

The set, $D$, contains any subset of $B$ with cardinality $i$, whose elements are pairwise disjoint. With $n=20, i=4$, it looks like this:
$\{\{\{1,2\},\{3,4\},\{5,6\},\{7,8\}\},\{\{1,2\},\{ 3,4\},\{5,6\},\{7,9\}\},\{\{1,2\},\{3,4\},\{5,6\}, \{7,10\}\},\text{...} \}$

I need to figure out:
1. How many elements of $D$ contains at least one element of $C_3$
2. How many elements of $D$ contains no element of $C_3$ and $k$ elements of $C_2$
For $k=0,1, \text{...} ,i$.

Since any element of $D$ is element of exactly one of the above described sets, the sum is the same
as the cardinality of $D$. With $(a)_i$ being the pochhammer symbol, $|D|$ is:
$\frac{2^i \left(1-\frac{n}{2}\right)_i \left(\frac{3}{2}-\frac{n}{2}\right)_i}{i!}$

I need to look through and count some stuff of $C_1,C_2,C_3$ to obtain what's needed to determine the result,
but I have no freaking idea about what and how to use it.. any ideas please?

2. ## Re: Counting subsets of disjoint sets

Maybe use Inclusion/Exclusion? Let $C_3 = \{X_1,X_2,\ldots, X_t\}$. Then, the number of elements of $D$ that contain at least one element of $C_3$ would be the number of elements of $D$ containing $X_1$ plus the number containing $X_2$ plus ... plus the number containing $X_t$, minus the number containing exactly two of the subsets, plus/minus ...