Results 1 to 5 of 5

Math Help - Number of relations?

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    21

    Number of relations?

    Consider the set F={1,2,3,4}. How many symmetric relations are R are there on F such that 1R2?

    My professor says the answer is 2^9 but I have no idea why.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by mjlaz View Post
    Consider the set F={1,2,3,4}. How many symmetric relations are R are there on F such that 1R2?
    My professor says the answer is 2^9.
    Do you understand that there are 2^{10} symmetric relations on F?
    If not, that is a place to start.
    Of those 2^{10} relations, 2^{9} contain the pair (1,2).
    Here is a file that may help you understand.
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2009
    Posts
    21
    Discrete has been giving me problems, particularly relations. I'm not seeing how there are 2^10 symmetric relations on F. Would it be too much trouble to explain?

    Regards,

    Marc
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by mjlaz View Post
    Discrete has been giving me problems, particularly relations. I'm not seeing how there are 2^10 symmetric relations on F.
    Did you read the attached file? The proof is in that file.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2009
    Posts
    23
    Hi, let me add to Plato...

    think of a relation on {1,2,3,4} as a 4 by 4 matrix over zeros
    and ones. This defines the relation when you think of
    i related to j if and only if the (i,j) entry of your matrix is a 1.
    So, in you matrix, (lets call the entries a_i,j) you must have a_1,2 = 1
    (since 1R2). Since it is symmetric, you also must have a_2,1 = 1.
    Now, you need to count the number of ways of filling the matrix
    with ones and zeros in such a way that it creates a legal relation
    (here, legal = symmetric). That is, whenever you decide on a value
    of a_ij then you need to put a_ji the same value. Thus,
    you may as well simply tell what the values above and on the diagonal are.
    But let's count how many entries there are above and on the
    diagonal: first row there are three (one is already specified),
    second row there are three, third row there are two, last row there is one.
    That's 3+3+2+1 = 9 altogether. By the multiplication principle
    of combinatorics, if you have 9 independent choices with two
    possible ways each, you have altogether 2 x 2 x 2 ... x 2 = 2^9
    ways of filling the matrix. That should be it. I guess it is somehow
    contained in Plato's remarks as well, I just thought I spell it out for you.

    Best,

    ZD
    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 relations
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: October 31st 2008, 05:46 AM
  5. Number of relations
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: September 16th 2008, 05:52 AM

Search Tags


/mathhelpforum @mathhelpforum