1yes,196 is correct
How many functions f : {1, 2, 3, 4, 5} to {1, 2, 3, 4, 5} satisfy f(f(x)) = f(x) for all x= {1, 2, 3, 4, 5} ?
-
UP 0 DOWN 0 0 17
17 Answers
341Ok. Let A = {1,2,3,4,5}=B. We are looking for functions f: A → B satisfying f(f(x)) = f(x).
Now for the sake of exploration, you see what happens if say f(1) =2.
Then f(f(1)) = f(2) = 2. By this it is clear that if 2 belongs to the range of f, then we must have f(2) = 2. You can extend this to say that this is true of any number a that appears in the range, i.e. f(a) = a.
If the function is onto then it is clear from the above discussion that the only function possible is f(x) = x.
What if its not onto? Let us say that only 1,4, and 5 appear in the range. I have conveyed this same idea as "1,4, and 5 have pre-images under f".
Its clear that f(1) =1, f(4) = 4, f(5)=5.
Now the question is how to assign f(2) and f(3) in such a way that the condition f(f(x)) = f(x) still holds?
Again, some exploration. Say f(2) =1. Then all that follows is that f(f(2)) = f(1) =1 and all izz well. That means f(2) can be randomly chosen from among {1,4,5}. The same thing holds true for f(3).
Now we have our strategy in place to construct any such function.
(1) Pick how many numbers appear in the range. Call this k. k can be 1,2,3,4 or 5. If k=5, the function is onto.
(2) Pick the k numbers that appear in the range. Let them be x1,...,xk
Then f(xk) = xk
(3) The remaining numbers i.e. xk+1,...,x5 may be be randomly assigned to {x1,...,xk} i.e. the remaining (5-k) numbers each have a choice of k numbers to be assigned to.
Its obvious that every such function is obtained by this procedure
Now, we only need to count how many functions are obtained this way.
The selection of the k numbers that appear in the range is 5Ck
The remaining (5-k) numbers have k valid choices each, which means it can independently be assigned in k5-k ways.
Then add up for each k i.e. k=1,2,3,4,5.
1is the answer 5 ? First tell me if I'm correct...........then I'll post the solution.
341I'll do that. But, I want to know if the answer is right.
First you have to choose the k numbers out of 5 that have a pre-image. that is 5Ck ways. The remaining (5-k) numbers in the domain can be assigned to any of the chosen k numbers. That assignment can be done in
\underbrace{k \ \times \ k \ \times \ ... \times \ k}_{\text{5-k times}} = k^{5-k}
ways.
Hence the number of functions with k numbers appearing in the range is \binom{5}{k} k^{5-k}
1prophet sir, i m not getting how you got that expression 5Ck (k)^(5-k) ?
62hmm.. got it my mistake is that i too only one one onto functions...
62My solution..
f(xi)=xj
then f(xj)=xi
so all we have to do is to find the number of ways we can select zero or more groups of 2 elements from (x1, x2... x5), for all other elements, f(xi)=xi
so 5C0+5C2+5C2x3C2/2
= 1 + 10 + 10x3/ 2 = 26
Dont know what is wrong with my logic... and to be true prophet sir I did not understand the proof given by you..
Let me try to read that one again...
341Suppose k numbers have a pre-image under f. Let them be x_1,...,x_k, 1≤k≤5
Then we must necessarily have f(x_i) = x_i for 1≤i≤k. Now to complete f, we can randomly assign xj for k+1≤j≤5 to any of the xi. You can easily verify that the conditions of the problem are indeed met.
The number of such functions is \binom {5}{k} k^{5-k}
Hence summing up over all k, we have the total number of functions as \sum_{k=1}^5 \binom {5}{k} k^{5-k} = 196