Let f:{1,2,3,4,5}→{1,2,3,4,5}, then the number of functions which are into and satisfy f(i)=i for at least one?
for at least one i=1,2,3,4,5 are
A)435
B)2121
C)2025
D)None of these
the ans is given as 2025 and i noe some sort of dearrangement is to be used.
I calc no. of into func=5^5 - 5!=3005
I cant exactly figure out how to proceed forward.
Detailed explanation would be appreciated.
More Questions From This User See All
Answers & Comments
Verified answer
It seems you're using "into" to mean "not onto". This isn't a usual definition at all - usually "into" would just clarify what the codomain is.
--------------
All right. I'll define the sets of functions
V = set of all functions {1,2,3,4,5}→{1,2,3,4,5}
A = set of all onto functions {1,2,3,4,5}→{1,2,3,4,5}
B = set of all functions {1,2,3,4,5}→{1,2,3,4,5} such that f(i)<>i for every i.
Then the set we want to count is
(V-A) n (V-B) = V - (AUB)
(where the above is just DeMorgan's law).
All right. Then we have
#( V - (AUB) ) = #(V) - #(A U B)
= #(V) - [ #(A) + #(B) - #(AnB) ]
= #(V) + #(AnB) - #(A) - #(B).
All of these are easier to compute than the original.
#(V) = 5^5 = 3125
#(A) = 5! = 120
#(B) = 4^5 = 1024
#(AnB) = round(5! / e) = 44
3125 + 44 - 120 - 1024 = 2025.
2025 = 45^2 or 9^2 * 5^2.
If you don't know how to get the answer, work it backwards.