374 views

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

1. Give the expression for $N_r$, in terms of n.
2. Give the expression for $N_f$, terms of n.
3. Which is larger for all possible $n$, $N_r$ or $N_f$
retagged | 374 views

no of binary relation = $2^{n^2}$
no of function = $n^n$

\begin{align} \quad&&& 2^{n^2} &&& n^{n}\end{align}
\begin{align} &n^{2} \log (2) &&&n \log(n) &&\text{ // apply,\logon both}\end{align}
\begin{align}&n^{2} \log (2)\quad > &n \log(n)\end{align}

No of relation > No of function

edited
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.

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.