Results 1 to 2 of 2

Math Help - Counting ordered k-tuples of subsets...

  1. #1
    Junior Member gusztav's Avatar
    Joined
    Jan 2008
    Posts
    48
    Awards
    1

    Counting ordered k-tuples of subsets...

    Hi,
    I would deeply appreciate any help with the following problem:

    Let S be a set with n elements, and k some natural number. Find the number of ordered k-tuples (S_1, ..., S_k) of subsets of S, such that:

    [problem 1] S_i \cap S_j = \emptyset,(\forall i \neq j)

    [problem 2] S_1 \cap ... \cap S_k = \emptyset

    [problem 3] S_1 \cup ... \cup S_k = S

    [problem 4] S_1 \cup ... \cup S_k = S,|S_i|=n_i,\sum_{i=1}^k n_i=n,S_i \cap S_j = \emptyset,(\forall i \neq j)

    *******

    I tried to make an example; let S=\{1,2,3,4,5,6,7\} so n=7, and let k=3. So, we have to find the number of all ordered triples (S_1,S_2,S_3) which satisfy above properties for each problem.

    Now, in [problem 1] we'd have to find the number of all ordered triples of subsets of S which are disjoint in pairs, some of them are ({1},{2,3},{6}) or ({3},{4},{7}) or ({1,2,3,4},{6},{7})...

    In [problem 2] we seek triples of subsets of S the intersection of which is empty. But isn't this the same as [problem 1]? It seems that, if all subsets are pairwise disjoint, then the intersection of all of them must be empty?

    In [problem 3] we look for the number of ordered triples of subsets of S which, in union, yield the whole S, such as ({1,2,3},{2,3,6,7},{1,4,5,6})

    The [problem 4] is similar to the [problem 3], the only difference being the requirement that all subsets in an ordered triple must be disjoint, e.g. ({1},{2,3,4,5},{6,7})

    *******

    I really have no idea where to start from, so I would be really grateful for your help and your time.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by gusztav View Post
    [problem 1] S_i \cap S_j = \emptyset,(\forall i \neq j)
    Let us examine k=3. Draw a Venn diagram with a square around it symbolizing the outside of S_1\cup S_2\cup S_3. Now there are 2^3 possible locations to put a number if you drew out the diagram. We need to put these n numbers into these locations in such a way that S_i \cap S_j = \emptyset i.e. so that no two circles intersect. That means a number can go into four remaining locations: either only into S_1 or S_2 or S_3 or completely outside the circles. Therefore we are placing n 'objects' into 4 'boxes' and the total number is {{n-4+1}\choose 4}

    If general we would have to draw k circles which partition the plane into 2^k regions. The total number of places to put the numbers is k+1. The number of ways of doing this is {{n-k}\choose {k+1}}

    Quote Originally Posted by gusztav View Post
    [problem 2] S_1 \cap ... \cap S_k = \emptyset
    No this is not the same as problem 1. This is included in problem 1 therefore the number would be smaller.

    Again draw the Venn diagrams for k circles. This time the numbers are being places anywhere except into the middle of where all three circles intersect. That leaves us with 2^k - 1 boxes where we place n numbers. The total number is therefore, {{n-2^k}\choose 2^k}

    Try doing the others ones.
    (This is how I get out of doing all the problems when I get lazy).
    Last edited by ThePerfectHacker; November 1st 2008 at 09:11 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: March 10th 2011, 09:22 AM
  2. Formalization of tuples
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 9th 2011, 02:31 AM
  3. Counting Subsets of a Finite Set
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: December 13th 2010, 11:16 PM
  4. Counting combinations of tuples with restrictions
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 14th 2009, 05:59 PM
  5. Vectors and K-tuples
    Posted in the Calculus Forum
    Replies: 0
    Last Post: September 7th 2009, 05:59 PM

Search Tags


/mathhelpforum @mathhelpforum