Question

Let A be a set of k (k>0) elements. Which is larger between the number of binary relations (say, Nr) on A and the number of functions (say, Nf) from A to A?

(a) number of relations

(b) number of functions

(c) the element set

(d) number of subsets of the relation

I have been asked this question in an interview.

The origin of the question is Types of Relations topic in portion Relations of Discrete Mathematics

Answer 1

Right answer is (a) number of relations

Explanation: For a set with k elements the number of binary relations should be 2^(n*n) and the number of functions should be n^n. Now, 2^(n*n) => n^2log (2) [taking log] and n^n => nlog (n) [taking log]. It is known that n^2log (2) > nlog (n). Hence, the number of binary relations > the number of functions i.e, Nr > Nf.