 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/discrete-mathematics-probability-and-continuous-mathematics/3/f/solution

n

(a, a)

can be chosen independently. For each of the

(2 n)

(a, b), (b, a)

occur or neither occurs. Every such choice is free and produces a distinct symmetric relation. Hence

2^{n} 2^{(2 n)} = 2^{n (n + 1) /2} .

For the empty set this correctly gives one binary relation, the empty one.

 New to topics? Read the docs here!