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 / ii

Table of contents
- Solution ii

Solution

A symmetric relation has

n

independent choices on the diagonal. For each of the

(2 n)

unordered pairs

{a, b}

of distinct elements, either both ordered pairs are included or neither is. Thus there are

2^{n + (2 n)}

symmetric relations, so the requested number is

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

 Ancestors (12)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version