 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/discrete-mathematics-continuous-mathematics-and-probability-resit/2/d/i/solution

There are

n^{2}

possible ordered pairs and hence

2^{n^{2}}

n

diagonal pairs, while its remaining

n^{2} - n

pairs are unrestricted. Subtracting the reflexive relations gives

2^{n^{2}} - 2^{n^{2} - n}

 New to topics? Read the docs here!