Consider the setF={1,2,3,4}. How many symmetric relations areRare there onFsuch that 1R2?

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

Thanks!

Printable View

- Apr 28th 2009, 08:06 AMmjlazNumber of relations?
Consider the set

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

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

Thanks! - Apr 28th 2009, 08:34 AMPlato
Do you understand that there are $\displaystyle 2^{10}$ symmetric relations on $\displaystyle F$?

If not, that is a place to start.

Of those $\displaystyle 2^{10}$ relations, $\displaystyle 2^{9}$ contain the pair $\displaystyle (1,2)$.

Here is a file that may help you understand. - Apr 28th 2009, 12:15 PMmjlaz
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 - Apr 28th 2009, 12:41 PMPlato
- Apr 28th 2009, 02:04 PMZeroDivisor
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