How to Calculate Symmetric Relations in Set Theory?

[jwxie]

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

Can someone guide me through how to approach the problem?

Thanks

 

[kompik]

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

Can someone guide me through how to approach the problem?

Thanks

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 $$\binom{7}{4}$$;
2 elements on the diagonal and 1 above it $$\binom72\binom{21}1$$;
no element on the diagonal and 2 above it $$\binom{21}2$$.

For 5 elements you have the following possibilieites:
All 5 elements on the diagonal $$\binom75$$;
3 elements on the diagonal and 1 above it $$\binom73+\binom{21}1$$;
1 element on the diagonal and 2 above it $$\binom71+\binom{21}2$$.