The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+6 votes
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$
asked in Set Theory & Algebra by Veteran (68.8k points)
retagged by | 374 views

2 Answers

+18 votes
Best answer

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, $\log$ on both}\end{align}$
$\begin{align}&n^{2} \log (2)\quad >   &n \log(n)\end{align}$

No of relation > No of function

answered by Veteran (49.1k points)
edited by
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.
0 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.

 

 

answered by Veteran (15.4k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

32,330 questions
39,146 answers
108,245 comments
36,501 users