Results 1 to 2 of 2

Thread: Counting subsets of disjoint sets

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    16

    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?
    Last edited by rousfv; Nov 23rd 2013 at 10:36 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,337
    Thanks
    1298

    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 ...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. 2 disjoint clsed subsets of (R^2)
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Aug 28th 2011, 04:09 AM
  2. Replies: 5
    Last Post: Mar 10th 2011, 08:22 AM
  3. Disjoint subsets countable
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: Jul 20th 2010, 01:41 PM
  4. disjoint subsets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 18th 2010, 04:28 PM
  5. Subsets that have a disjoint
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Feb 8th 2010, 10:02 AM

Search Tags


/mathhelpforum @mathhelpforum