How many symmetric relations are there for an $n$-element set?
Thank you.
combinatoricsrelations
asked 2010-12-21
user id:5023
101
22gold badges44silver badges55bronze badges
0
When you say relation, do you mean it has to include all the $n$ elements in it, or is the empty relation (for example) is also counted - as it satisfies symmetry. – 2010-12-21
0
all the Symmetric relations, including the empty relation. For instance, A={1,2} then the symmetric relations are: empty set, {(1,1)},{(1,2),(2,1)} etc. – 2010-12-21
4
This has a homework feel to it - is it? Since I don't just want to give the answer, here's a good hint: how many total relations are there for an n-element set, and what do they correspond to? Now, what do the symmetric relations correspond to, and can you use that to find your answer? – 2010-12-21
1
@Qiaochu I thought we agreed that if the OP doesn't say it's homework then we can't assume it is. In the past people have been flamed for asking what Steven is asking above. Do we have a new policy on, now that the elections are over? – 2010-12-21
0
Steven, the number of all relations could be seen as the number of all the matrices of nxn, where every entry in the matrix could be either 0 or 1 - therefore, by the multiplication principle there is a total of 2^(n^2). From here, I don't see how to find the number of all the symmetric relations - I just know that it has to be symmetric from the diagonal or on the diagonal. – 2010-12-21
0
@Yuval: I did not agree to such a policy. If you like you can restart the thread on meta, but I am being consistent with my statements during the election. @Anonymous: use the multiplication principle again. What does symmetry across the diagonal tell you about which entries are redundant? – 2010-12-21
0
@Qiaochu: all the matrices such that the the [ij]!=[ji], where [ij] represent the element on row i column j. If I'm correct, how do I use the multiplication principle here? – 2010-12-21
0
@Anonymous: so which entries can you freely fill in such that they determine the rest of the entries? – 2010-12-21
0
@Qiaochu: all the matrices such that [ij]=[ji]. – 2010-12-21
0
Qiaochu: How can I continue from here? – 2010-12-21
3 Answers
3
Related Posts
[12139] Number of relations that are both symmetric and reflexive