Surjective functions and partitions.

[Stephen88]

Let A be the set of all functions f:{1,2,3,4,5}->{1,2,3} and for i=1,2,3 let Ai denote a subset of the functions f:{1,2,3,4,5}->{1,2,3}\i.

i)What is the size of :
1). A,
2).the sizes of its subsets Ai,and
3).Ai\capAj (i<j) also
4).A1\capA2\capA3.

ii)Find with justification the number of surjective functions f:{1,2,3,4,5}->{1,2,3}.

iii)Explain how each surjective function gives a 3-partiton of f:{1,2,3,4,5}

iv)How many 3-partitons of f:{1,2,3,4,5} are there altogethere?

Answers.
i)1).3^5...2).2^5 each 3).1^5 each...4).0
ii)We can use stirling numbers of the second kind to find this out S(5,3).
iii)Because the image of the function is made up of 3 elements?
iv)I don't know...I"m still thingking the same as for part ii)

 

[lanedance]

hey Stephen88 can you clarify how the Ai subsets are defined? its not exactly clear to me in the question

Is Aj the subset of functions that only map
f \in A_i \iff f:{1,2,3,4,5}-&gt;{1,2,3}\i

so A_1 is given by
f \in A_1 \iff f:{1,2,3,4,5}-&gt;{2,3}

If so
1,2,3,4 look ok

so a surjective function is onto, meaning it must map at least one x to each y

 

[lanedance]

ii) have to admit I didn't know about Stirling Numbers but googling a Stirling number of the second kind is exactly the way to partition n (5) objects into k (3) non-emtpy subset, which makes sense. As I've not used them explicitly I would be careful to check how repetitions are counted...as an example the partition:
1 | 2 | 345
could be expressed as 6 = 3! different surjective functions

Another way that may work is to count functions that are not surjective and subtract from the total number of functions

iii) partition the initial set based on image element, you could show that this gives an equivalence class an so a partition

iv) consider the point on counting in ii)

 

[wisvuze]

Question number ii) shouldn't be too hard to do without deriving the stirling formula of the second kind.

Try counting all surjections from X -> Y where X has a cardinality 1 greater than Y ( ex. X: {1,2,3,4} , Y : {1,2,3} ). This case should help you generalize into the case where the size of X is 2 greater than Y ( ex. X:{1,2,3,4,5} Y : {1,2,3} ) Make sure you account for "overcounts"