1. Number of relations

Hey,
How many full relations are there on the set {1,...n}?
A full relations is a relation R such that for every i in {1,2,...n} there exists a j in {1,...n} such that (i,j) belongs to R.

2. Re: Number of relations

Originally Posted by hedi
How many full relations are there on the set {1,...n}?
A full relations is a relation R such that for every i in {1,2,...n} there exists a j in {1,...n} such that (i,j) belongs to R.
By that definition a full relation is one where its domain is the set and its codomain is nonempty.
Say $N=\{1,2,\cdots, n\}$ so $\mathcal{R}=N\times B$ where $B\in\mathscr{P}(N)\setminus\emptyset$. [$\mathscr{P}(N)$ being the powerset of $N$]
Thus you need to know how many nonempty subsets $N$ has.

3. Re: Number of relations

This is not true.For example for n=3 R={(1,1),(1,2),(2,1),(2,3),(3,3)} is full relation on {1,2,3} but there is not such B.Rather, it is the union of {i}xAi for Ai in P(N)/{empty set},i=1,...,n.How many element are in this union?

4. Re: Number of relations

I suppose it is the number of(A1,A2,...,An)'s such that Ai belong to P([n])/{empty set}, that is (2^n-1)^n

5. Re: Number of relations

Originally Posted by hedi
This is not true.For example for n=3 R={(1,1),(1,2),(2,1),(2,3),(3,3)} is full relation on {1,2,3} but there is not such B.Rather, it is the union of {i}xAi for Ai in P(N)/{empty set},i=1,...,n.How many element are in this union?
Thank you for the correction. Clearly I misunderstood the definition of a full relation. (BTW i have never seen this term before.)
So if this is your example: $\{(1,1),(1,2),(2,1),(2,3),(3,3)\}=[\{1\}\times\{1,2\}] \cup[\{2\}\times \{2,3\}] \cup[\{3\}\times\{3\}]$ Do you agree?
If you do then in this example $\mathcal{R}=[\{1\}\times A] \cup[\{2\}\times B] \cup[\{3\}\times C]$, where each of $A,~B,~\&~C$ is a nonempty subset of $\{1,2,3\}$
Then that is a complete listing of all possible of what your course is calling a full relation.
I make for $n=3$ the total full relations to be $(2^3-1)^3$.
Can you explain HOW? WHY?

6. Re: Number of relations

yes,i wrote this formula above for general n,you can see.