Let S={1,2,3,4}. Find the number of functions such that for all .

Printable View

- Oct 22nd 2008, 12:34 PMalexmahoneNumber of functions
Let S={1,2,3,4}. Find the number of functions such that for all .

- Oct 22nd 2008, 01:01 PMPlato
- Oct 22nd 2008, 01:13 PMPlato
- Oct 22nd 2008, 01:15 PMMoo
- Oct 22nd 2008, 01:25 PMPlato
And also:

- Oct 22nd 2008, 01:34 PMPlato
- Oct 22nd 2008, 03:28 PMPlato
There are possible functions .

Each of those functions is a set of four pairs: .

But the pair must be there! (WHY?)

Suppose that . Then in order for .

BUT so . 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 - Oct 23rd 2008, 12:49 AMalexmahoneMy 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? - Oct 23rd 2008, 03:42 AMPlato
That is what I got also.