GATE CSE 2002 | Question: 3

Question

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$

• A. Give the expression for $N_r,$ in terms of $n.$
• B. Give the expression for $N_f,$ terms of $n.$
• C. Which is larger for all possible $n,N_r$ or $N_f$

Comments

A relation on a set S={1,2,3} → {(1,2),(1,3)} this is a relation but not a function.

Every function is a relation but converse is false.

Answer 1

x wrong

you cannot do like this bcz it is For all n - so you can't apply asymptotic method as it's only meant for all "sufficiently large" n.

this method is wrong.