2.4.1. Part (a): Counting Functions

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₂, …, xₘ} and the elements of Y = {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 so on. So, there are n possibilities when it comes to assigning an image for an element xᵢ. And the image for xⱼ and the image for xₖ are independently picked.

In this section, we explore how to count the number of functions that can be formed from one set to another. If we have two sets, X with m elements and Y with n elements, we can create various functions from X to Y. A function requires assigning each element in set X an output from set Y. For each individual element in X, there are n choices from Y. Since each choice is independent of others, the total number of functions can be calculated using the formula n^m, where m is the number of elements in X. For example, if X has 2 elements and Y has 3 elements, then the number of possible functions is 3^2 = 9.

Think of a school where there are 2 students (set X) and 3 different grades they could receive (set Y). Each student can independently receive any grade out of the 3 available. So, Student 1 can get A, B, or C, and Student 2 can also get A, B, or C. The total combinations of grades (functions) they can receive is 3 x 3 = 9 different possible outcomes.

Part b asked you to find out the number of injective functions from the set X to the set Y. Now we cannot say that the images for every element xᵢ is 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 the image for x₁, I have n possibilities. But once I have decided the image for x₁, I cannot assign that image to be a possible image for element x₂, that is why for x₂ I have n - 1 possible images. Likewise, for the mth element from the set X, I can only assign n - m + 1 possible images. So, the total number of injective functions will be n × (n - 1) × (n - 2) × ... × (n - m + 1).

Here, we look at injective functions, which are special because each element from the domain (set X) must map to a unique element in the codomain (set Y). This means that no two different inputs can produce the same output. Initially, for the first element from X, we have n choices in Y. However, for the second element in X, we now only have n - 1 choices, since we can't repeat the first choice. Continuing this pattern, for the third element we would have n - 2 choices, and so forth. Therefore, the formula for counting injective functions turns out to be the product of decreasing choices from n, which results in n × (n - 1) × ... until we've assigned all m elements from X. For instance, if X has 3 elements and Y has 5, the number of injective functions would be 5 × 4 × 3 = 60.

Imagine a scenario where you have 3 employees (set X) competing for 5 different awards (set Y). Since no two employees can win the same award, the first employee has 5 award options. When it comes to the second employee, they have only 4 remaining choices (one award is already given out), and the third employee has 3 awards left to choose from. The total number of ways you could assign unique awards to the employees would be 5 × 4 × 3 = 60.

Part c asks you to find out the number of bijective functions from X to Y. The first thing to observe here is that for a bijection from X to Y we need |X| = |Y|. It is very easy to verify that if their cardinalities are different, then we cannot have a one-to-one and onto mapping. If the cardinality of X and Y is the same, then any bijection can be viewed as a permutation of the elements. For n elements in both sets, this means there are n! (n factorial) possible ways to map all elements from X to Y uniquely.

This chunk covers bijections, where a function is both injective and surjective, meaning every element in set Y is paired with exactly one element in set X. The essential condition for a bijection is that both sets must have the same number of elements. Thus, if both X and Y have n elements, any bijective function can be reinterpreted as a unique arrangement (or permutation) of elements from set X to set Y. The total number of arrangements of n elements is n!, which is the factorial of n, calculated as n × (n - 1) × ... × 2 × 1. For example, if both sets contain 4 elements, the number of bijections is 4! = 24.

Consider a classroom with 4 students (set X) and 4 unique chairs (set Y). If each student must sit in a different chair, you can think of all the possible seating arrangements as bijective functions. The ways to arrange the students in chairs is 4! = 24; each student can occupy any chair without sharing, producing multiple distinct arrangements.

--