Results 1 to 7 of 7

Math Help - Counting Sets

  1. #1
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307

    Counting Sets

    Determine with proof the number of ordered triples  (A_1, A_2, A_3) of sets which have the property (i)  A_1 \cup A_2 \cup A_3 = \{1,2,3,4,5,6,7,8,9,10 \} and (ii)  A_1 \cap A_2 \cap A_3 = \emptyset . So basically this means that all the sets are disjoint.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    So basically this means that all the sets are disjoint.
    Not, necessarily. A=\{1\},B=\{1,...,9\}, C=\{10\}. But that actually makes the problem easier!


    Quote Originally Posted by tukeywilliams View Post
    Determine with proof the number of ordered triples  (A_1, A_2, A_3) of sets which have the property (i)  A_1 \cup A_2 \cup A_3 = \{1,2,3,4,5,6,7,8,9,10 \} and (ii)  A_1 \cap A_2 \cap A_3 = \emptyset .
    Think of a Venn diagram, see below.

    Now the numbers \{1,2,3,4,5,6,7,8,9,10\} can be placed anyway except into the shaded area. So we are placing 10 "marbles" into 6 "boxes" (because there are 7 sections and we omit the middle section). The formula is:
    {{6+10-1}\choose 10}
    Attached Thumbnails Attached Thumbnails Counting Sets-picture26.gif  
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    Could you also use matrices to solve this problem?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by tukeywilliams View Post
    Could you also use matrices to solve this problem?
    I really have no idea? I am not a Combinatorics expert .

    Perhaps, you can phrase this problem as a Graph Theory problem and then arrive at your answer by computing the adjancency matrix. But I have no idea how to do that.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    I was thinking that we could somehow use a binary relation. So there is some type of mapping (maybe a bijection?) between  A_1 \cup A_2 \cup A_3 = \{1, \ldots, 10\} ,  A_1 \cap A_2 \cap A_3 = \emptyset and some type of  10 \times 3 matrix with  0,1 so that there are no rows that are  \{000 \} or  \{111 \} .
    Last edited by tukeywilliams; July 25th 2007 at 08:35 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    I think there are  6 possibilities for each row and therefore  6^{10} total possible triples?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,384
    Thanks
    1475
    Awards
    1
    Quote Originally Posted by tukeywilliams View Post
    I think there are  6 possibilities for each row and therefore  6^{10} total possible triples?
    On a strict reading of this problem as stated, I agree that the answer is 6^{10}.

    However, are you sure that you have stated this question correctly?
    As stated, the question has several different readings.
    I have seen this sort of question many times: “How many ways can {0,1,2,…,8,9} be partitioned into three non-empty, pair-wise disjoint sets?”
    Could that be what was meant by this question?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Counting Sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 21st 2010, 03:39 AM
  2. counting sets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 10th 2009, 03:41 PM
  3. sets and counting
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 3rd 2009, 09:08 PM
  4. G-sets to counting
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: December 15th 2008, 11:52 AM
  5. Sets and counting
    Posted in the Advanced Algebra Forum
    Replies: 8
    Last Post: March 7th 2006, 03:35 AM

Search Tags


/mathhelpforum @mathhelpforum