Let S={1,2,3,4}. Find the number of functions such that for all .
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
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?