Results 1 to 6 of 6

Math Help - Number of relations

  1. #1
    Newbie
    Joined
    Sep 2008
    Posts
    3

    Number of relations

    Okay. So I really need to understand how to do this problem, because nowhere does it say anything in my text about finding the number of relations. Thanks.

    Let A = {1,2,3,4,5} and B = {w,x,y,z}
    How many relations that
    (i) contain (1,w)?
    (ii) do not contain (5,z)
    (iii) contain (1,w) but not (5,z)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by jasone View Post
    Okay. So I really need to understand how to do this problem, because nowhere does it say anything in my text about finding the number of relations. Thanks.

    Let A = {1,2,3,4,5} and B = {w,x,y,z}
    How many relations that
    (i) contain (1,w)?
    (ii) do not contain (5,z)
    (iii) contain (1,w) but not (5,z)
    are there any restrictions on our relations? do they have to be functions? etc
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2008
    Posts
    3
    That's all the question said.

    I can see that some of the relations from A to B are the empty set, {(1,w)}, {(1,x)}, {(1,w), (1,x)}, {(2,w), (3,z), (5,x)}, and A x B, for example.

    A x B = {(1,w), (1,x), (1,y), (1,z), (2,w), (2,x), (2,y), (2,z), (3,w), ... , (5,y), (5,z)}

    But how do I count all of the relations that have (1,w), for instance?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by jasone View Post
    That's all the question said.

    I can see that some of the relations from A to B are the empty set, {(1,w)}, {(1,x)}, {(1,w), (1,x)}, {(2,w), (3,z), (5,x)}, and A x B, for example.

    A x B = {(1,w), (1,x), (1,y), (1,z), (2,w), (2,x), (2,y), (2,z), (3,w), ... , (5,y), (5,z)}

    But how do I count all of the relations that have (1,w), for instance?
    note that |A x B| = 5(4) = 20

    so lets say we want relations with (1,w), how can we find all of them?

    well, one is {(1,w)}

    then we can make one with (1,w) and 1 of the other elements, then one with (1, w) and 2 of the other elements, then one with (1,w) and 3 of the other elements, ...., and finally one with (1,w) and all of the other 19 elements.

    how would you count all of those?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2008
    Posts
    3
    I got the series 1 (being {(1,w)}) + 19 (choices for a 2nd element) + 19C2 (2 other choices) + 19C3 + ... + 19C17 + 19 + 1
    So the finite sum (from i=0 to n=19) nCi would get the answer?

    Or in other words, 2^19 = 524288. Is that right?

    And for part (ii), I tried 1 (being the empty set) + 19 (choices for one element) + 19C2 + ... + 19C17 + 19 + 1 (all 19 elements).

    In other words, again, 2^19. Same answer. Is that right?

    And for part (iii), 1 + 18 + 18C2 etc for an answer of 2^18.

    Did I do all of this correctly?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,384
    Thanks
    1475
    Awards
    1
    Quote Originally Posted by jasone View Post
    Okay. So I really need to understand how to do this problem, because nowhere does it say anything in my text about finding the number of relations.
    Let A = {1,2,3,4,5} and B = {w,x,y,z}, How many relations that
    (i) contain (1,w)?
    (ii) do not contain (5,z)
    (iii) contain (1,w) but not (5,z)
    This problem always affords such a wonderful teaching opportunity. I cannot resist.

    As already noted, there are a total of 2^{20} possible relations from A to B.
    These are often called binary relations. This problem in part shows why.
    Any one of the relations either contains the pair (1,w) or it does not. Think binary.
    So half of the total number of relations contains the pair and half do not.
    Half of 2^{20} is 2^{19}. That answers both (i) & (ii).
    Half of the relations containing (1,w) also contain (5,z), half do not.
    Again, half of 2^{19} is 2^{18}.
    Note that 2^{18} is one fourth of 2^{20}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relations and Functions - Inverse Relations Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 13th 2011, 12:20 PM
  2. Replies: 1
    Last Post: September 19th 2011, 01:09 PM
  3. Determining number of relations on a set
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: December 8th 2010, 09:42 AM
  4. Number of relations?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 28th 2009, 02:04 PM
  5. Number relations
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: October 31st 2008, 05:46 AM

Search Tags


/mathhelpforum @mathhelpforum