# FunctionsWatch

This discussion is closed.
#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
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
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
#4
Thanks a lot people. I'll look into Stirling's formula.

Euclid
0
14 years ago
#5
Look up Stirling Numbers. Stirling's formula is a different matter - used to approximate n!
0
#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
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

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

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

### 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
Wed, 30 Jan '19
• Solent University
Sat, 2 Feb '19

### Poll

Join the discussion

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