Question #94826
The number of partitions of {1, 2, 3, 4, 5} into three blocks is S(5, 3) = 25. The total number of functions f : {1, 2, 3, 4, 5} ! {1, 2, 3, 4} with |Image(f)| = 3 is
1
Expert's answer
2019-09-19T11:57:10-0400

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),\

S(5,3)=34241/2(341)=81161/2(811)=25S(5,3)=3^4-2^4-1/2(3^4-1)=\\ 81-16-1/2(81-1)=25

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 432=244\cdot 3\cdot 2=24.

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 2524=600.25\cdot 24 = 600.

Answer: The total number of functions is 600.


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!
LATEST TUTORIALS
APPROVED BY CLIENTS