If A has n elements, what is the number of symmetric relations on A?

Correct answer: 2^{n(n+1)/2}

Correct answer: A. A relation on an n-element set is a subset of A × A. There are n diagonal pairs (a,a). Each diagonal pair may independently be included or omitted, giving 2^n choices. For two distinct elements, symmetry requires that (a,b) and (b,a) are treated together: either both are included or both are omitted. The number of unordered pairs of distinct elements is C(n,2)=n(n−1)/2, so these pairs contribute 2^{n(n−1)/2} choices. Multiplying the independent choices gives 2^n × 2^{n(n−1)/2} = 2^{[2n+n(n−1)]/2} = 2^{n(n+1)/2}. Therefore option A is correct. Option B omits the diagonal choices and also does not represent the symmetric pairing correctly. Option C counts every relation without imposing symmetry. Option D is not the number of subsets of ordered pairs and has no valid basis here. Memory cue: a symmetric relation is chosen by one decision for each diagonal pair and one decision for each unordered pair of distinct elements.