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

[Micand]

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³ and that there are 3² 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. Choose x = 2 or x = 3. (2 ways.)
2. Map f(1) to x. (1 way.)
3. Map f(x) to 3. (1 way.)
4. Map remaining input to any of three outputs. (3 ways.)

This yields 2*1*1*3 = 6 functions with (f ∘ f)(1) = 3, but 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 take the following 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. Is this correct? Is there a more reasonable way to go about it?

Any assistance you can offer will be much appreciated. Thanks!

 

[Jhero]

Your approach for the first problem is correct. For the second problem, you are also correct. A more intuitive way to think about it is to note that for any given function f, there can only be one function g such that (f∘g)(1) = 3. This is because the output of g is determined by the input of f, and the output of f must be 3 in order for the composition to have an output of 3 at 1. Therefore, the total number of ordered pairs (f,g) that satisfy the condition is equal to the total number of functions in F_3, which is 33. Hope this helps!