Every function is a relation but every relation is not a function.So, clearly relation size is greater than that of number of function.

The Gateway to Computer Science Excellence

+14 votes

Let $A$ be a set of $n(>0)$ elements. Let $N_r$ be the number of binary relations on $A$ and let $N_f$ be the number of functions from $A$ to $A$

- Give the expression for $N_r,$ in terms of $n.$
- Give the expression for $N_f,$ terms of $n.$
- Which is larger for all possible $n,N_r$ or $N_f$

+27 votes

Best answer

A. Consider a $2D$ matrix of $n\times n$ size where each dimension represent the $n$ elements of $A.$ So, we get $n^2$ elements where each one can be viewed as an ordered pair $(i,j), 1\leq i,j \leq n.$ Now if we consider a set with these $n^2$ elements, any subset of it will be a binary relation from $A$ to $A$.

So, no. of binary relations, $N_r = 2^{n^2}$

For a function from a set of $n$ elements to a set of $m$ elements we have $m$ choice for each of the $n$ elements of the domain. Thus we get $m^n$ possibilities. Here, $m = n.$ So,

No. of functions, $N_f = n^n$

Now, number of functions must be smaller than the number of relations because every function is also a relation. We can prove this formally as follows:

$\lim_{n\to \infty} \dfrac{2^{n^2}}{n^n} $

$\dfrac{\infty}{\infty} \text{ form}.$ So, applying L'Hopital's rule (Limit remains same after taking derivative of both numerator and denominator)

$= \lim_{n \to \infty} \dfrac{2n.\log 2. 2^{n^2}}{nn^{n-1}}$

We can continue like this applying L'Hopital's rule and we should eventually get $1$ in the denominator (as after each derivation power of $n$ decreases by $1$) which gives the limit value as $\infty.$ So, $2^{n^2}$ is faster growing than $n^n.$

So, for sufficiently large $n,$ $N_r > N_f$

+22

Here, no need to do further calculation which one is greater. A function is a subset of relation.

Every function is a relation but every relation is not a function.So, clearly relation size is greater than that of number of function.

Every function is a relation but every relation is not a function.So, clearly relation size is greater than that of number of function.

0

Yup.. functions are a subset of relations. But I think the explanation given in the answer is wrong, the denominator does not decrease at all.

+1

@Ayush Upadhyaya functions is a subset of relations because one to many type of relations are excluded from being functions right?

+4 votes

**A. **Number of binary relations on set A = **Nr = 2^(n^2)**

**B.** Number of functions on set A =** Nf = n^n**

**C. No of relation > No of function( Nr >Nf) **,because function is restricted version of relation so it is obvious.By the way, we can check by taking **log**** **at both sides.

0 votes

$N_r = 2^{n^{2}}$ as total elements in the Cartesian product is $n \times n$ out of which each entry may or may not be included in the relation.

$N_f = n^{n}$ Each element can map to any of the n elements.

Take log of both the $N_f = n^{n}$ and $N_r = 2^{n^{2}}$

we get $n* log n $ and $n^2 log2$ we know that $n^2 log2$ > $n* log n $ so $N_r$ > $N_f$

$N_f = n^{n}$ Each element can map to any of the n elements.

Take log of both the $N_f = n^{n}$ and $N_r = 2^{n^{2}}$

we get $n* log n $ and $n^2 log2$ we know that $n^2 log2$ > $n* log n $ so $N_r$ > $N_f$

52,218 questions

59,882 answers

201,076 comments

118,121 users