Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How many symmetric relations?

  1. May 9, 2010 #1
    Hi.

    Let A = 1,2,3,4,5,6,7
    How many symmetric relations on A contain exactly (a) four ordered pairs, (b) 5 , (c) seven and (d) eight

    The book has solutions to the first two, which I didn't understand at all.

    Please look the pic below
    scymv4.png

    Can someone guide me through how to approach the problem?

    Thanks
     
  2. jcsd
  3. May 11, 2010 #2
    You can imagine any relation a a table with 7 rows and 7 columns, where you indicate in each position whether the corresponding elements belong to the relation. (This is basically the same as working with the graph of this relation.)

    A relation is symmetric if and only if this graph/table is symmetric with respect to the main diagonal. Hence, a symmetric relation is uniquely determined by the pairs on and above the main diagonal.
    You have 7 positions on diagonal and 21=6+5+4+3+2+1 positions above the diagonal.
    If you put a elements above the diagonal, then there are also a elements bellow it, by the symmetry. So, by putting a elements above the diagonal and b elements on the diagonal, you obtain a relation consisting of 2a+b pairs.

    Now, if you want to have 4 elements you have these possibilities:
    all 4 elements are on the diagonal [tex]\binom{7}{4}[/tex];
    2 elements on the diagonal and 1 above it [tex]\binom72\binom{21}1[/tex];
    no element on the diagonal and 2 above it [tex]\binom{21}2[/tex].

    For 5 elements you have the following possibilieites:
    All 5 elements on the diagonal [tex]\binom75[/tex];
    3 elements on the diagonal and 1 above it [tex]\binom73+\binom{21}1[/tex];
    1 element on the diagonal and 2 above it [tex]\binom71+\binom{21}2[/tex].
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook