In question 8 part (a), (b), (c) we are supposed to count certain things. So, you are given two sets X and Y consisting of m and n number of elements. So, I am calling the elements of X = { x₁, …, xₘ} and the elements of Y = { y₁, …, yₙ}. We are supposed to find out the number of functions from X → Y. It turns out that the number of functions will be n^m, why so? Because when we want to build a function from the set X → Y, each element x from the set X has to be assigned an image that is the definition of a function. Now how many ways I can assign an image for the element x₁? Well I can assign y₁ as the possible image for x₁, I can pick y₂ as the possible image for x₁ and in the same way, I can pick yₓ as a possible image for the element x₁. So, there are n possibilities when it comes to assigning image for an element x₁. And the image for x₂ and the image for x₃ are independently picked; there is no dependency between the images of x₁ and images of x₂. Based on all these observations, we can say that I have n number of possibilities when it comes to assigning image for x₁. And like that for each of the elements from the set X, I have n possible images which I can choose. Therefore, the number of functions is n * n * ... (m times), which is nothing but n^m.

Part b asked you to find out the number of injective functions from the set X to the set Y. Well, we will be using more or less a similar argument that we used for part A except that now we cannot say that the images for every element x must be chosen independently. Because now we are counting or we are interested in the injective functions and in injective functions, for every distinct element x from the set X, you have to assign a unique image. You cannot have both x₁ and x₂ getting mapped to the same element in the Y set. So, that is why when it comes to selecting an image for x₁, I have n possibilities. But once I have decided the image for the element x₁, I cannot assign that image to be a possible image for element x₂. Thus, for x₂, I have (n - 1) possible images, and this pattern continues. When I am assigning the image for the m-th element from the X set, that image has to be different from all the images which I have selected for the previous elements of the X sets.

Part c asks you to find out the number of bijective functions from X to Y. So, the first thing to observe here is that for a bijection from X to Y we need |X| = |Y|. If their cardinalities are different, then we cannot have a one-to-one and onto mapping from the X set to the Y set. Now if the cardinality of the X and the Y set are the same (m = n), any bijection from the X set to Y set can be considered a permutation of the elements from X to Y. The number of permutations we can have for n elements is n!, so that will be the number of bijective functions from the set X to the set Y.

In part d of question 8 we are introducing a function, the S function, called the Stirling function of type 2. This function takes two input values, r and s, and denotes the number of ways of partitioning an r-element set into s non-empty disjoint subsets, given that s ≤ r. This means we have a bigger set called A where |A| = r and we want to find out how many ways we can split this set into s number of disjoint subsets.

Using this Stirling function, we have to count the number of surjective functions possible from set X to set Y. Since we are interested in finding out the number of surjective functions, we know that in a surjective function, each element from the codomain set should have at least one pre-image. We can denote the set of pre-images for any element y from the codomain, which consists of elements from set X. When analyzing a surjective function, these pre-image sets form a partition of the domain set X. Counting how many partitions we can form from set X into n non-empty disjoint subsets gives us the value Stirling function S(m, n). Each permutation of those partitions corresponds to a unique surjective function.