The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+8 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

  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 (69k points)
retagged by | 402 views

2 Answers

+20 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 (54k 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.
+2 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 (16.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

34,194 questions
40,882 answers
39,775 users