Answer to Question #94826 in Combinatorics | Number Theory for Abdulrazaq Sani Ibrahim

Question

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

Answer 1

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)=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 $4\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 $25\cdot 24 = 600.$

Answer: The total number of functions is 600.