# Counting subsets of disjoint sets

• Nov 23rd 2013, 10:33 AM
rousfv
Counting subsets of disjoint sets
The set, $\displaystyle A$, contains numbers: $\displaystyle \{1,2,\text{...},n\}$.
The set, $\displaystyle B$, contains any subset of $\displaystyle A$ with cardinality $\displaystyle 2$: $\displaystyle \{\{1,2\},\{1,3\},\text{...},\{n-1,n\}\}$
$\displaystyle C_1,C_2,C_3$ are some pairwise disjoint sets that satisfy $\displaystyle C_1\cup C_2\cup C_3=B$.

The set, $\displaystyle D$, contains any subset of $\displaystyle B$ with cardinality $\displaystyle i$, whose elements are pairwise disjoint. With $\displaystyle n=20, i=4$, it looks like this:
$\displaystyle \{\{\{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 $\displaystyle D$ contains at least one element of $\displaystyle C_3$
2. How many elements of $\displaystyle D$ contains no element of $\displaystyle C_3$ and $\displaystyle k$ elements of $\displaystyle C_2$
For $\displaystyle k=0,1, \text{...} ,i$.

Since any element of $\displaystyle D$ is element of exactly one of the above described sets, the sum is the same
as the cardinality of $\displaystyle D$. With $\displaystyle (a)_i$ being the pochhammer symbol, $\displaystyle |D|$ is:
$\displaystyle \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 $\displaystyle 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?
• Nov 23rd 2013, 11:10 AM
SlipEternal
Re: Counting subsets of disjoint sets
Maybe use Inclusion/Exclusion? Let $\displaystyle C_3 = \{X_1,X_2,\ldots, X_t\}$. Then, the number of elements of $\displaystyle D$ that contain at least one element of $\displaystyle C_3$ would be the number of elements of $\displaystyle D$ containing $\displaystyle X_1$ plus the number containing $\displaystyle X_2$ plus ... plus the number containing $\displaystyle X_t$, minus the number containing exactly two of the subsets, plus/minus ...