Results 1 to 4 of 4

Math Help - Partitions for surjective functions

  1. #1
    Junior Member
    Joined
    Feb 2011
    Posts
    25

    Partitions for surjective functions

    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).AiAj (i<j) also
    4).A1A2A3.

    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 thinking the same as for part ii)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Partitions for surjective functions

    Some notation. If f:A\to B and C\subseteq B then f^{-1}[C]=\{x\in A:~f(x)\in C\}.

    It can be shown that if f is a surjection then the collection \left\{ {f^{ - 1} \left[ {\{ y\} } \right]:{\kern 1pt} y \in B} \right\} is a partition of A

    So is your #iv correct?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2011
    Posts
    25

    Re: Partitions for surjective functions

    ah...yes...there 3 in total .....I have the partitions properties in my head I can't describe them here because of the LaTex.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Partitions for surjective functions

    Quote Originally Posted by StefanM View Post
    ah...yes...there 3 in total .....I have the partitions properties in my head I can't describe them here because of the LaTex.
    Well there are more than three.
    There are 150 surjections from a set of five to a set of three.
    Each of those surjections defines a three-cell partition of the set of five.

    If \phi:\{1,2,3,4,5\}\to\{1,2,3\} is a surjection then \left\{ {\phi ^{ - 1} (\{ 1\} ),\phi ^{ - 1} (\{ 2\} ),\phi ^{ - 1} (\{ 3\} )} \right\} is a partition of \{1,2,3,4,5\}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Surjective functions
    Posted in the Advanced Math Topics Forum
    Replies: 3
    Last Post: November 4th 2009, 03:51 PM
  2. Prooving surjective and injective functions
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: October 20th 2009, 01:51 PM
  3. Replies: 1
    Last Post: September 21st 2009, 08:01 PM
  4. calculate total of surjective functions
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: March 17th 2009, 03:29 PM
  5. Generating Functions and Integer Partitions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 9th 2008, 08:28 AM

Search Tags


/mathhelpforum @mathhelpforum