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. (Punch)
Thanks!
Printable View
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. (Punch)
Thanks!
Do you understand that there areQuote:
Originally Posted by mjlaz
symmetric relations on
?
If not, that is a place to start.
Of thosecontain the pair
.
Here is a file that may help you understand.
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
Did you read the attached file? The proof is in that file.Quote:
Originally Posted by mjlaz
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