Results 1 to 2 of 2

Math Help - Counting subsets of disjoint sets

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    16

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

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,845
    Thanks
    715

    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 ...
    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: August 28th 2011, 04:09 AM
  2. Replies: 5
    Last Post: March 10th 2011, 08:22 AM
  3. Disjoint subsets countable
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: July 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: February 8th 2010, 10:02 AM

Search Tags


/mathhelpforum @mathhelpforum