Results 1 to 6 of 6

Math Help - Counting functions on the set {1, 2, 3}

  1. #1
    Newbie
    Joined
    Apr 2011
    Posts
    3

    Counting functions on the set {1, 2, 3}

    Hello!

    I'm unsure of how to attack the following problem. It states that F_{3} denotes the set of all functions from {1, 2, 3} to {1, 2, 3}, then asks one to find the number of functions f F_{3} such that (f ∘ f)(1) = 3. Simpler questions are clear to me -- I see, for example, that the total number of functions is 3^3 and that there are 3^2 functions where f(1) = 3 -- but I'm not sure of a reasonable way to find how many have (f ∘ f)(1) = 3. I drew out the full tree of 27 possible functions to find that there are six such possible functions, then reasoned backward to the following process:

    1. Make f(2) = 1 or f(3) = 1. (2 ways.)
    2. Make f(1) = 3. (1 way.)
    3. Map remaining input onto any one of three outputs. (3 ways)


    This yields 2*3 = 6 functions with (f ∘ f)(1) = 3, but this method seems wrong, and so I question whether there's a more intuitive way to go about it.

    The second related problem I'm struggling with asks one to find the number of ordered pairs (f, g) of functions in F_{3} so that (f ∘ g)(1) = 3. On this one, I have no idea where to begin.

    Any assistance you can offer will be much appreciated. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,801
    Thanks
    1691
    Awards
    1
    Quote Originally Posted by Micand View Post
    It states that F_{3} denotes the set of all functions from {1, 2, 3} to {1, 2, 3}, then asks one to find the number of functions f\in F_{3} such that (f ∘ f)(1) = 3.
    Any function that has the pairs \{(1,2),(2,3),(3,X)\} has that property. So there are three of those.

    Any other function that has the pairs \{(1,3),(2,X),(3,3)\} also has that property. So there are three of those.

    Can you find any other function?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2011
    Posts
    3
    Quote Originally Posted by Plato View Post
    Any function that has the pairs \{(1,2),(2,3),(3,X)\} has that property. So there are three of those.

    Any other function that has the pairs \{(1,3),(2,X),(3,3)\} also has that property. So there are three of those.

    Can you find any other function?
    Thank you for your reply, Plato. I can't find any other function -- as I understand it, f(1) must map to 2 or 3, because if it maps to 1, then f(f(1)) = 1. If f(1) = 2, then f(2) must be 3, and f(3) may be any of three values; if f(1) = 3, then f(3) must be 3, and f(2) may be any of three values. This yields the six -- and only the six -- functions you mention in your post. Am I correct?

    In the second problem ("find the number of ordered pairs (f, g) of functions in F_{3} so that (f ∘ g)(1) = 3"), I tried this approach:

    1. Choose x = 1, 2, or 3. (3 ways.)
    2. Map g(1) to x. (1 way.)
    3. Map f(x) to 3. (1 way.)
    4. Map g(2) and g(3) to any of three outputs. (3*3 ways.)
    5. Map other two f inputs to any of three outputs. (3*3 ways.)


    This yields 3*1*1*(3*3)*(3*3) = 243 functions. I'm not sure whether I'm on the right track, though, and if I am, whether there's a better way to go about it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,801
    Thanks
    1691
    Awards
    1
    Quote Originally Posted by Micand View Post
    In the second problem ("find the number of ordered pairs (f, g) of functions in F_{3} so that (f ∘ g)(1) = 3"), I tried this approach:
    Suppose that Z=1,~2,\text{ or }3 then you need two functions such that (1,Z)\in g\text{ and }(Z,3)\in f.
    That would mean that (1,3)\in f\circ g.
    How many pairs (g,f) have those properties?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2011
    Posts
    3
    Quote Originally Posted by Plato View Post
    Suppose that Z=1,~2,\text{ or }3 then you need two functions such that (1,Z)\in g\text{ and }(Z,3)\in f.
    That would mean that (1,3)\in f\circ g.
    How many pairs (g,f) have those properties?
    Thank you once more. If I understand correctly, if Z=1,~2,\text{ or }3, then there are three possibilities for the ordered pairs (1,Z)\in g\text{ and }(Z,3)\in f. As each of the two unmapped inputs in f and g must then be mapped to one of three possible outputs, there are 3(3^2)(3^2) = 3^5 = 243 pairs (g,f) that have the desired properties. A small Python program I wrote agrees:

    Code:
    def test_functions(functions):
      for f in functions:
        for g in functions:
          if f[g[1]] == 3:
            print f, g, f[g[1]]
    
    def make_functions():
      functions = []
      for i in range(1, 4):
        for j in range(1, 4):
          for k in range(1, 4):
            functions.append({1: i, 2: j, 3: k})
      return functions
    
    
    test_functions(make_functions())
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,801
    Thanks
    1691
    Awards
    1
    Quote Originally Posted by Micand View Post
    As each of the two unmapped inputs in f and g must then be mapped to one of three possible outputs, there are 3(3^2)(3^2) = 3^5 = 243 pairs (g,f) that have the desired properties.
    That is correct. I hope that I have given you a different way of looking at these problems.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Counting onto functions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 27th 2011, 02:23 AM
  2. Counting Zeroes of Complex Functions
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: November 14th 2010, 01:12 AM
  3. Counting functions problem 4
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 3rd 2010, 01:58 PM
  4. Counting
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: November 6th 2009, 01:26 PM
  5. Counting!
    Posted in the Statistics Forum
    Replies: 2
    Last Post: June 18th 2008, 07:11 AM

Search Tags


/mathhelpforum @mathhelpforum