Number of functions

Printable View

October 22nd 2008, 11:34 AM
alexmahone

Number of functions

Let S={1,2,3,4}. Find the number of functions $f: S \to S$ such that $f(f(x)) = 1$ for all $x \in S$ .
October 22nd 2008, 12:01 PM
Plato

Quote:

Originally Posted by alexmahone

Let S={1,2,3,4}. Find the number of functions $f: S \to S$ such that $f(f(x)) = 1$ for all $x \in S$ .

How many do you think there are?
Here is one: $f:\left\{ {\left( {1,1} \right),\left( {2,1} \right),\left( {3,1} \right),\left( {4,1} \right)} \right\}$
October 22nd 2008, 12:13 PM
Plato

Quote:

Originally Posted by alexmahone

I think the answer is one; is that right?

Well, I gave you one. Can you find another?
October 22nd 2008, 12:15 PM
Moo

Quote:

Originally Posted by alexmahone

I think the answer is one; is that right?

What about :

$f(1)=1$
$f(2)=1$
$f(3)=2$
$f(4)=2$
?

And
$f(1)=1$
$f(2)=1$
$f(3)=4,2$
$f(4)=1$

and several more...
October 22nd 2008, 12:25 PM
Plato

And also:
$f:\left\{ {\left( {1,1} \right),\left( {2,1} \right),\left( {3,1} \right),\left( {4,2} \right)} \right\}$
$f:\left\{ {\left( {1,1} \right),\left( {2,1} \right),\left( {3,1} \right),\left( {4,3} \right)} \right\}$
October 22nd 2008, 12:34 PM
Plato

Quote:

Originally Posted by alexmahone

Any hints on how to go about counting, you guys?

My goodess, how many hints do you need?
October 22nd 2008, 02:28 PM
Plato

There are $4^4 = 256$ possible functions $\left\{ {1,2,3,4} \right\} \mapsto \left\{ {1,2,3,4} \right\}$ .
Each of those functions is a set of four pairs: $f:\left\{ {\left( {1,\_} \right),\left( {2,\_} \right),\left( {3,\_} \right),\left( {4,\_} \right)} \right\}$ .
But the pair $(1,1)$ must be there! (WHY?)
Suppose that $f(1) = 2$ . Then in order for $f(f(1)) = 1 \Rightarrow \quad f(2) = 1$ .
BUT $f(f(2)) = f(1) = 2 \ne 1$ so $f(1) \ne 2$ . Thus only (1,1)

Another pair must have 1 as its second term.
What else is necessary?
If you work this out you will learn something about combinatorics
October 22nd 2008, 11:49 PM
alexmahone

My solution

The problem requires the following (obvious) conditions:
1) f(1)=1.
2) No element other than 1 can be mapped onto itself.
3) Atleast one of f(2), f(3), f(4) is equal to 1.

So f(2) can take 3 possible values:

Case 1: f(2)=1
If f(3)=1, f(4)=1 or 2 or 3
If f(3)=2, f(4)=1 or 2
If f(3)=4, f(4)=1

6 functions

Case 2: f(2)=3
f(3)=1 (forced)
f(4)=1 or 3

2 functions

Case 3: f(2)=4
f(4)=1 (forced)
f(3)=1 or 4

2 functions

Total=6+2+2=10 functions

Is that right?
October 23rd 2008, 02:42 AM
Plato

That is what I got also.