# Thread: Counting functions on the set {1, 2, 3}

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

Hello!

I'm unsure of how to attack the following problem. It states that $\displaystyle 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 ∊ $\displaystyle 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 $\displaystyle 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!

2. Originally Posted by Micand
It states that $\displaystyle 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 $\displaystyle f\in F_{3}$ such that (f ∘ f)(1) = 3.
Any function that has the pairs $\displaystyle \{(1,2),(2,3),(3,X)\}$ has that property. So there are three of those.

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

Can you find any other function?

3. Originally Posted by Plato
Any function that has the pairs $\displaystyle \{(1,2),(2,3),(3,X)\}$ has that property. So there are three of those.

Any other function that has the pairs $\displaystyle \{(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 $\displaystyle 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.

4. Originally Posted by Micand
In the second problem ("find the number of ordered pairs (f, g) of functions in $\displaystyle F_{3}$ so that (f ∘ g)(1) = 3"), I tried this approach:
Suppose that $\displaystyle Z=1,~2,\text{ or }3$ then you need two functions such that $\displaystyle (1,Z)\in g\text{ and }(Z,3)\in f$.
That would mean that $\displaystyle (1,3)\in f\circ g$.
How many pairs $\displaystyle (g,f)$ have those properties?

5. Originally Posted by Plato
Suppose that $\displaystyle Z=1,~2,\text{ or }3$ then you need two functions such that $\displaystyle (1,Z)\in g\text{ and }(Z,3)\in f$.
That would mean that $\displaystyle (1,3)\in f\circ g$.
How many pairs $\displaystyle (g,f)$ have those properties?
Thank you once more. If I understand correctly, if $\displaystyle Z=1,~2,\text{ or }3$, then there are three possibilities for the ordered pairs $\displaystyle (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 $\displaystyle (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())

6. Originally Posted by Micand
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 $\displaystyle (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.