Results 1 to 9 of 9

Math Help - Number of functions

  1. #1
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Number of functions

    Let S={1,2,3,4}. Find the number of functions f: S \to S such that f(f(x)) = 1 for all x \in S.
    Last edited by alexmahone; October 23rd 2008 at 03:34 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,648
    Thanks
    1596
    Awards
    1
    Quote Originally Posted by alexmahone View Post
    Let S={1,2,3,4}. Find the number of functions f: S \to S such that f(f(x)) = 1 for all x \in S.
    How many do you think there are?
    Here is one: f:\left\{ {\left( {1,1} \right),\left( {2,1} \right),\left( {3,1} \right),\left( {4,1} \right)} \right\}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,648
    Thanks
    1596
    Awards
    1
    Quote Originally Posted by alexmahone View Post
    I think the answer is one; is that right?
    Well, I gave you one. Can you find another?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by alexmahone View Post
    I think the answer is one; is that right?
    What about :

    f(1)=1
    f(2)=1
    f(3)=2
    f(4)=2
    ?

    And
    f(1)=1
    f(2)=1
    f(3)=4,2
    f(4)=1

    and several more...
    Last edited by Moo; October 22nd 2008 at 12:28 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,648
    Thanks
    1596
    Awards
    1
    And also:
    f:\left\{ {\left( {1,1} \right),\left( {2,1} \right),\left( {3,1} \right),\left( {4,2} \right)} \right\}
    f:\left\{ {\left( {1,1} \right),\left( {2,1} \right),\left( {3,1} \right),\left( {4,3} \right)} \right\}
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,648
    Thanks
    1596
    Awards
    1
    Quote Originally Posted by alexmahone View Post
    Any hints on how to go about counting, you guys?
    My goodess, how many hints do you need?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,648
    Thanks
    1596
    Awards
    1
    There are 4^4 = 256 possible functions \left\{ {1,2,3,4} \right\} \mapsto \left\{ {1,2,3,4} \right\}.
    Each of those functions is a set of four pairs: f:\left\{ {\left( {1,\_} \right),\left( {2,\_} \right),\left( {3,\_} \right),\left( {4,\_} \right)} \right\}.
    But the pair (1,1) must be there! (WHY?)
    Suppose that f(1) = 2. Then in order for f(f(1)) = 1 \Rightarrow \quad f(2) = 1.
    BUT f(f(2)) = f(1) = 2 \ne 1 so f(1) \ne 2. Thus only (1,1)

    Another pair must have 1 as its second term.
    What else is necessary?
    If you work this out you will learn something about combinatorics
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    My solution

    The problem requires the following (obvious) conditions:
    1) f(1)=1.
    2) No element other than 1 can be mapped onto itself.
    3) Atleast one of f(2), f(3), f(4) is equal to 1.

    So f(2) can take 3 possible values:

    Case 1: f(2)=1
    If f(3)=1, f(4)=1 or 2 or 3
    If f(3)=2, f(4)=1 or 2
    If f(3)=4, f(4)=1

    6 functions

    Case 2: f(2)=3
    f(3)=1 (forced)
    f(4)=1 or 3

    2 functions

    Case 3: f(2)=4
    f(4)=1 (forced)
    f(3)=1 or 4

    2 functions

    Total=6+2+2=10 functions

    Is that right?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,648
    Thanks
    1596
    Awards
    1
    That is what I got also.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of functions from one set to another?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 8th 2011, 09:46 AM
  2. Replies: 2
    Last Post: August 19th 2010, 09:32 PM
  3. number of functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 16th 2010, 10:23 AM
  4. Replies: 5
    Last Post: October 7th 2008, 12:55 PM
  5. Number of Functions
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 25th 2008, 11:17 AM

Search Tags


/mathhelpforum @mathhelpforum