Sets... Discrete Math.. Please Help!?

Question

How many symmetric relations are there on a set with eight elements?

Answer 1

Symmetric relations are alot like "graphs" in discrete mathematics. You could characterize a graph:

http://en.wikipedia.org/wiki/Graph_theor...

As a set of vertices with a symmetric relationship on them.

Now, as for the question, say you have the numbers 1 through 8. Those can be the 8 elements.

For the number 1, what question can you ask? Is 1 related to 2? Is 2 related to 1? But because the relation is symmetric, that's the same question.

So the question is really, do you relate 2 and 1 or don't you? What about 2 and 3? What about 2 and 2 (an object can be related to itself).

So how many element-to-element relations are possible? There are 8 elements, so there are 8C2 = 28 possible pairs. There are also 8 more possible relations between an element and itself.

So with 28+8=36 possible ways to relate one thing to another, you can choose for each one whether it is related or not. To give you an idea of this process, consider:

1) Is 1 related to 1? [Yes or no - 2 choices]

2) Is 1 related to 2? [Yes or no - 2 choices]

3) Is 1 related to 3? [Yes or no - 2 choices]

...

9) Is 1 related to 8? [Yes or no - 2 choices]

10) Is 2 related to 2? [Yes or no - 2 choices]

11) Is 2 related to 3? [Yes or no - 2 choices]

...

36) Is 8 related to 8?  [Yes or no - 2 choices]

This leaves you with 36 things with 2 choices each. The total number of ways to do this is:

2^36 = 68 719 476 736

Answer 2

symmetric sets  are defined as

X   ( a b c d)   (x,y) belongs to R  and also (y,x) belongs to R

in this case w get 4 symmetric sets

( a,a) (b,c) ( c,b) ( d,d) .

however  fro ex

(1,2,3,4) and x < y then  2,3 is a valid  symmetric set but 3,2 is not.