The number of partitions of {1, 2, 3, 4, 5} into three blocks is S(5, 3)=25.
S(5,3) is Stirling number of the second kind, there is formula for S(n,3):
S(n,3)=3^{n-1}-2^{n-1}-1/2(3^{n-1}-1),\
Let {A,B,C} be partition of {1, 2, 3, 4, 5} into three blocks, so that elements of different blocks have different images.
For example, if A={1,2,3}, B={4}, C={5}, we can have function f: f(1) = f(2) = f(3) = 1, f(4) = 3, f(4) = 4.
There are 4 possibilities (one element of the set {1,2,3,4}) to set image for elements of A, after that for B we will have 3 possible values and for C we will have 2, therefore the number of injective functions from {A,B,C} to {1, 2, 3, 4} is .
We are given that there are S(5, 3) = 25 partitions of {1, 2, 3, 4, 5} into three blocks and for each partition there are 24 functions, hence the total number of functions f is
Answer: The total number of functions is 600.
Comments