Problem 59 - 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|=3,|B|=2$$

Step-by-Step Solution

Answer

The number of possible surjections from set \(A\) to set \(B\) with cardinalities \(|A|=3, |B|=2\) is 2.

Step 1: Identify the values of n and r

In this problem, we are given that \(|A|=3\) and \(|B|=2\). So the values of \(n\) and \(r\) are: \[n = 3\] \[r = 2\]

Step 2: Calculate S(n, r) using the Stirling number formula

The Stirling number of the second kind, \(S(n, r)\), can be computed using the following formula for non-negative integers \(n\) and \(r\): \[ S(n, r) = \frac{1}{r!} \sum_{k=0}^{r}(-1)^k {r \choose k}(r-k)^n \] Calculation for the given values of \(n\) and \(r\): \[S(3, 2) = \frac{1}{2!} \sum_{k=0}^{2}(-1)^k {2 \choose k}(2-k)^3 \] \[S(3, 2) = \frac{1}{2} [(1)(1^3) - (2)(1^2) + (1)(0^3)] = 1 \]

Step 3: Calculate the number of surjections

Now we can find the number of surjections from set \(A\) to set \(B\) using the formula \(r{!} S(n, r)\). Since we found that \(S(3, 2) = 1\), the number of surjections for the given cardinalities of the sets is: \(2! \cdot S(3, 2) = 2! \cdot 1 = 2\)

Step 4: Final answer

The number of possible surjections from set \(A\) to set \(B\) with cardinalities \(|A|=3, |B|=2\) is 2.

Key Concepts

Stirling Numbers

Stirling numbers of the second kind, denoted as \( S(n, r) \), help us understand partitioning of sets. They count the number of ways to divide a set of \( n \) elements into \( r \) non-empty subsets. This is essential in combinatorics, particularly when dealing with mappings like surjections.
\( S(n, r) \) can be calculated using a specific formula:

• Each partition must be non-empty.
• The formula involves a sum over binomial coefficients, alternate signs and powers, which can be expressed as:\[S(n, r) = \frac{1}{r!} \sum_{k=0}^{r}(-1)^k {r \choose k}(r-k)^n\]
• This formula balances out the need for non-empty partitions by taking into account all possible configurations.

This concept is significant when determining the number of surjective functions between two finite sets, as it ensures all elements in the range have a pre-image.

Finite Set

A finite set, as the name suggests, has a limited number of elements. Set theory often deals with identifying and counting the elements in such sets.
For example:

• A set \( A \) with \(|A| = 3 \) has three elements.
• Similarly, a set \( B \) with \(|B| = 2 \) has two elements.

Understanding the concept of finite sets is crucial in solving problems related to mappings, such as surjective functions. The problem of determining surjections, or total onto functions, between finite sets becomes more manageable when using tools like Stirling numbers. Working with finite sets allows us to apply concrete counting methods to find a solution. In the context of our exercise, finite sets \( A \) and \( B \) make it possible to derive the number of surjective functions clearly.

Combinatorics

Combinatorics is the branch of mathematics focused on counting, arrangement, and combination of elements within a set. It is especially useful in analyzing mathematical structures by breaking them down into simpler components.
In our exercise, combinatorics plays a critical role in:

• Assessing and deriving the number of surjections from a set \( A \) to set \( B \).
• Using tools like Stirling numbers to figure out complex partitioning problems.
• Applying factorial calculations \( r! \) helps to find permutations within the function mappings.

Overall, combinatorics provides a structured approach to solving problems involving finite sets, making it indispensable in both theoretical and applied mathematics. Breaking down the problem related to surjections onto finite sets is only possible through combinatorial analysis, highlighting its importance in mathematical problem-solving.