Functions Watch

This discussion is closed.
Gauss
Badges: 2
Rep:
?
#1
Report Thread starter 14 years ago
#1
Hey people, I need help understanding the following, so please if you can explain your working instead of just posting a solution. Thanks!

The Set S has m elements and T has n elements.

a) How many functions are there from S to T?
b) How many of these are injective?
c) Assume m >= n. How many of these are surjective?
d) i) How many relations are there on S?
ii) How many of these are equivalence relations?
0
RichE
Badges: 15
Rep:
?
#2
Report 14 years ago
#2
(Original post by Euclid)
Hey people, I need help understanding the following, so please if you can explain your working instead of just posting a solution. Thanks!

The Set S has m elements and T has n elements.

a) How many functions are there from S to T?
b) How many of these are injective?
c) Assume m >= n. How many of these are surjective?
d) i) How many relations are there on S?
ii) How many of these are equivalence relations?
List the elements of S as 1,2,...,m.

(a) n^m as there are n choices for f(1), n for f(2),..., n for f(m) and these are independent choices.

(b) n choices for f(1), n-1 for f(2) (as this has to be different from f(1)), ...

so answer is n(n-1)(n-2)...(n-m+1) = n!/(n-m)!

(c) This is rather hard and the answer needs to be given in terms of the how many partitions there are of S into n parts. The answer is then n! times this number. I don't think there's a simple formula for this. [May be wrong about this though.]

(d) There are 2^(m^2) as a binary relation is a subset of S x S which has m^2 elements.

For the second part there are as many equivalence relations as there are partitions of S. Again I don't think there's a simple closed expression for this, though there is a generating formula.
0
Jonny W
Badges: 8
Rep:
?
#3
Report 14 years ago
#3
(Original post by RichE)
(c) This is rather hard and the answer needs to be given in terms of the how many partitions there are of S into n parts. The answer is then n! times this number. I don't think there's a simple formula for this. [May be wrong about this though.]
Yes, it is Stirling2(m, n)*n!, where Stirling2(m, n) is a Stirling number of the second kind. There is no closed form; if there were then there would be a closed form for the Stirling numbers.
(Original post by RichE)
(d) There are 2^(m^2) as a binary relation is a subset of S x S which has m^2 elements.

For the second part there are as many equivalence relations as there are partitions of S. Again I don't think there's a simple closed expression for this, though there is a generating formula.
Since we're using Stirling numbers, we can say (sum from i = 1 to m) Stirling2(m, i)
0
Gauss
Badges: 2
Rep:
?
#4
Report Thread starter 14 years ago
#4
Thanks a lot people. I'll look into Stirling's formula.

Euclid
0
RichE
Badges: 15
Rep:
?
#5
Report 14 years ago
#5
Look up Stirling Numbers. Stirling's formula is a different matter - used to approximate n!
0
Gauss
Badges: 2
Rep:
?
#6
Report Thread starter 14 years ago
#6
(Original post by RichE)
Look up Stirling Numbers. Stirling's formula is a different matter - used to approximate n!
Oh right, thanks.

One more question; in my question part d) I wrote "How many relations are there on S". Do you automatically assume the questions asking "How many binary relations are there on S"? Or is it always binary unless it says it is equivalence?

Euclid
0
RichE
Badges: 15
Rep:
?
#7
Report 14 years ago
#7
(Original post by Euclid)
Oh right, thanks.

One more question; in my question part d) I wrote "How many relations are there on S". Do you automatically assume the questions asking "How many binary relations are there on S"? Or is it always binary unless it says it is equivalence?

Euclid
Saying just "relation" tends to imply "binary relation", though there are "n-ary" relations, which correspond to subsets of S^n, and which take n inputs and return True or False. There are other special types of binary relations as well - e.g. partial orders.
0
X
new posts
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

University open days

  • University of East Anglia
    All Departments Open 13:00-17:00. Find out more about our diverse range of subject areas and career progression in the Arts & Humanities, Social Sciences, Medicine & Health Sciences, and the Sciences. Postgraduate
    Wed, 30 Jan '19
  • Aston University
    Postgraduate Open Day Postgraduate
    Wed, 30 Jan '19
  • Solent University
    Careers in maritime Undergraduate
    Sat, 2 Feb '19

Brexit: Given the chance now, would you vote leave or remain?

Remain (809)
80.42%
Leave (197)
19.58%

Watched Threads

View All
Latest
My Feed