1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Surjective functions and partitions.

  1. Aug 21, 2011 #1
    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[itex]\cap[/itex]Aj (i<j) also

    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?

    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)
  2. jcsd
  3. Aug 22, 2011 #2


    User Avatar
    Homework Helper

    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
    [tex] f \in A_i \iff f:{1,2,3,4,5}->{1,2,3}\i [/tex]

    so A_1 is given by
    [tex] f \in A_1 \iff f:{1,2,3,4,5}->{2,3} [/tex]

    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
    Last edited: Aug 22, 2011
  4. Aug 22, 2011 #3


    User Avatar
    Homework Helper

    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)
    Last edited: Aug 22, 2011
  5. Aug 22, 2011 #4
    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"
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook