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

• Apr 27th 2011, 09:25 AM
Micand
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!
• Apr 27th 2011, 09:39 AM
Plato
Quote:

Originally Posted by Micand
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?
• Apr 27th 2011, 10:21 AM
Micand
Quote:

Originally Posted by Plato
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.
• Apr 27th 2011, 10:30 AM
Plato
Quote:

Originally Posted by Micand
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?
• Apr 27th 2011, 12:04 PM
Micand
Quote:

Originally Posted by Plato
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())
• Apr 27th 2011, 12:32 PM
Plato
Quote:

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 $(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.