Hello!
I'm unsure of how to attack the following problem. It states that denotes the set of all functions from {1, 2, 3} to {1, 2, 3}, then asks one to find the number of functions f ∊ 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:
- Make f(2) = 1 or f(3) = 1. (2 ways.)
- Make f(1) = 3. (1 way.)
- 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 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!
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 so that (f ∘ g)(1) = 3"), I tried this approach:
- Choose x = 1, 2, or 3. (3 ways.)
- Map g(1) to x. (1 way.)
- Map f(x) to 3. (1 way.)
- Map g(2) and g(3) to any of three outputs. (3*3 ways.)
- 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.
Thank you once more. If I understand correctly, if , then there are three possibilities for the ordered pairs . 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 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())