2.4. Question 8: Functions from Set X to Set Y

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.

When counting the number of functions that map elements from one set (X) to another set (Y), we realize that each element in set X needs to point to exactly one element in set Y. For a set X with m elements and a set Y with n elements, we start by considering the first element in X. It has n choices in Y for which it can map to. This reasoning applies to every subsequent element in X. Since the choices made for mapping do not affect one another, we multiply the number of options available for each element, resulting in n * n * ... (m times) = n^m.

Imagine you have a box of m different colored balls (set X) and a box of n different colored baskets (set Y). For each ball, you can choose any one of the baskets to put it in. The first ball has n choices (it can go in any of the baskets), the second ball also has n choices, and so forth until all balls are placed. Therefore, if you have 3 balls and 4 baskets, you could organize the balls into the baskets in 4^3 (or 64) different ways.

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.

To find the number of injective (or one-to-one) functions from set X to set Y, we need to ensure that every element in X maps uniquely to an element in Y without repeating any images. For the first element in X, we still have n choices. However, for the second element, the choice is reduced to (n-1) because that element can no longer point to the same image as the first element. For the third element, this number decreases to (n-2), and so on until the last element in X, leading to the product n * (n - 1) * (n - 2) * ... * (n - m + 1).

Consider a classroom with m students (set X) and n different awards (set Y). If the awards are to be given such that each student receives a unique award (no sharing), the first student can choose any of the n awards, but the next student can only choose from (n - 1) remaining awards, and this continues until all students have unique awards. This scenario illustrates that some choices become limited as more students receive awards.

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.

A bijective function establishes a perfect pairing between every element in set X and every element in set Y, meaning each element of X corresponds to one and only one element of Y and vice versa. This can only occur if both sets are of equal size. Once confirmed that the sizes of both sets are the same (m = n), each possible mapping is effectively a rearrangement (or permutation) of the elements of X. The total number of these rearrangements for n items is calculated using factorial notation, denoted as n!. Thus, the number of bijective functions equals n!.

Think of a game where you have n friends (set X) who each want to wear a different colored T-shirt (set Y), and there are just enough shirts for everyone. If you want to assign each shirt to a friend, and each shirt can be worn by only one friend, every arrangement of friends to shirts is a unique way to achieve this. The total arrangements of friends wearing shirts can be represented as n!, which illustrates the different ways you can assign T-shirts when each one is distinctly chosen.

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.

The Stirling function of the second kind is crucial in combinatorics as it provides a way to count how many different ways we can organize or partition a given set into a specified number of non-empty groups. Particularly, it emphasizes the importance of ensuring no group is empty, thus focusing on practical partitions that still reflect underlying mathematical structures. The numeric representation S(r, s) gives the count for the various disjoint arrangements.

Consider you have r = 5 different-flavored ice creams and you want to form s = 3 groups for an ice cream party. The Stirling function tells you how many unique groupings can be made with at least one scoop of each flavor in a group. This scenario helps visualize the function's use in everyday decision-making, such as organizing flavors for a varied-taste experience!

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.

In order to ascertain the number of surjective functions, we first express the requirement that every element of Y must be hit by at least one element from X. Each surjective function can be viewed as a collection of pre-image subsets corresponding to each element in Y, which collectively partition X. Thus, the task transforms into counting how many ways we can partition set X into non-empty subsets. This value is retrieved with the Stirling number S(m, n). Furthermore, each arrangement or permutation of these subsets contributes to the total quantity of surjective functions.

Imagine a carnival where you have m different players (children) who all want to partake in n different games (like ring toss, balloon darts, etc.). However, for fairness, every game must have at least one player participating. The Stirling number would quantify the different ways to assign players to games such that no game gets left out, factoring in the permutations of players assigned to each game.

--