combinatrics

Ok. 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 x₁,...,x_k

Then f(x_k) = x_k

(3) The remaining numbers i.e. x_k+1,...,x₅ may be be randomly assigned to {x₁,...,x_k} 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 ⁵C_k

The remaining (5-k) numbers have k valid choices each, which means it can independently be assigned in k^5-k ways.

Then add up for each k i.e. k=1,2,3,4,5.

particularly which part is not clear to you?

prophet sir, i m still not clear with the solution,,please help!!

is the answer 5 ? First tell me if I'm correct...........then I'll post the solution.

I'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 ⁵C_k 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}

prophet sir, i m not getting how you got that expression 5Ck (k)^(5-k) ?

is the answer 31 ?? not sure//

no