Problem 60 - Discrete Mathematics with Applications

Question

The number of surjections that can be defined from a finite set \(A\) to a finite set \(B\) is given by \(r ! S(n, r),\) where \(|A|=n\) and \(|B|=r .\) Compute the number of possible surjections from \(A\) to \(B\) if: $$|A|=4,|B|=2$$

Step-by-Step Solution

Answer

There are 14 possible surjections from set A to set B if \(|A|=4\) and \(|B|=2\).

Step 1: To find the Stirling numbers of the second kind \(S(n, r)\), we can use the recursive formula: \[ S(n, r) = r \cdot S(n-1, r) + S(n-1, r-1) \] with base cases \(S(0, 0) = 1\), \(S(n, 0) = 0\), and \(S(0, r) = 0\) for \(r > 0\). We want to find \(S(4, 2)\). Using the recursive formula, we first find the intermediate values: \(S(3, 1)\), \(S(3, 2)\), and \(S(2, 1)\). #Step 2: Calculate intermediate Stirling numbers of the second kind#

To find these intermediate values, we can use the recursive formula again: 1. \(S(3, 1) = 1\cdot S(2, 1) + S(2, 0) = 1\cdot S(2, 1) = 1\cdot 1 = 1\) 2. \(S(3, 2) = 2\cdot S(2, 2) + S(2, 1) = 2\cdot S(2, 2) + 1\) (Note that \(S(2, 2) = 1\) as it implies each element in set B is paired with exactly one element in set A) So, \(S(3, 2) = 2\cdot 1 + 1 = 3\) 3. \(S(2, 1) = 1\) (as mentioned above) #Step 3: Calculate the final Stirling number of the second kind#

Step 2: Now we can find \(S(4, 2)\) using the previous results: \(S(4, 2) = 2\cdot S(3, 2) + S(3, 1) = 2 \cdot 3 + 1 = 7\) #Step 4: Calculate the number of surjections from set A to set B using the formula#

We will use the formula \(r{!} S(n, r)\) to calculate the number of surjections from set \(A\) to set \(B\). In this case, we have \(r = 2\) and \(S(4, 2) = 7\), so: Number of surjections = \(2{!} \cdot S(4, 2) = 2 \cdot 7 = 14\) Solution: There are 14 possible surjections from set A to set B if \(|A|=4\) and \(|B|=2\).

Key Concepts

Stirling numbers of the second kind

Stirling numbers of the second kind, denoted as \( S(n, r) \), play a pivotal role in combinatorics, specifically in problems dealing with partitioning. Imagine you have a set with \( n \) distinct items, and you want to divide this set into \( r \) non-empty, distinct subsets. \( S(n, r) \) tells you the number of ways this can be done.

One real-world analogy could be thinking of \( n \) students and trying to form \( r \) different study groups where no student is left out, and each group has at least one member. The value of \( S(4, 2) \) in the context of our exercise represents the different ways 4 students can be divided into 2 separate study groups, providing us with 7 distinct arrangements.

Recursive formula for Stirling numbers

Understanding the recursive nature of Stirling numbers is vital for iterative computation. The recursive formula for Stirling numbers is given by: \[ S(n, r) = r \cdot S(n-1, r) + S(n-1, r-1) \]. This succinct relationship allows us to build up the solution for higher values of \( n \) and \( r \) using the known values of Stirling numbers for smaller sets.

For instance, if we want to find out \( S(4, 2) \), we don't start from scratch. We use values from \( S(3, 2) \) and \( S(3, 1) \), as computed in the solution steps of the exercise. Here's a simpler way to understand it: You're assembling a puzzle, and the recursive formula gives you pieces that are already put together, which you can use to construct larger sections of the puzzle, eventually leading to the final image—or in our case, the Stirling number we're trying to calculate.

Set theory

At the foundation of the entire discussion about surjections and Stirling numbers lies set theory, an area of mathematical logic that studies sets, which are collections of objects. The concept of functions, including surjections, injections, and bijections, is deeply rooted in set theory, as they define various ways of mapping elements from one set to another.

A surjection is a function from one set, say set \( A \), to another set, set \( B \), where every element of set \( B \) is mapped to by at least one element of set \( A \). When the problem asks for the number of surjections from \( |A|=4 \) to \( |B|=2 \), it essentially asks in how many unique ways you can ensure that each member of set \( B \) has at least one pre-image in set \( A \)—a fundamental question in set theory applied to solving real combinatorial problems.