Problem 21 - Discrete Mathematics with Applications

Question

Find the number of ways of dividing a set of size \(n\) into two disjoint subsets of sizes \(r\) and \(n-r\).

Step-by-Step Solution

Answer

In order to divide a set of size \(n\) into two disjoint subsets of sizes \(r\) and \(n-r\), there are \(C(n, r) = \frac{n!}{r!(n-r)!}\) ways to do so, where \(C(n, r)\) represents the number of ways of selecting a combination of \(r\) objects from a set of \(n\) objects without taking order into account.

Step 1: Understand the Problem

We are given a set of size n, and we want to divide it into two disjoint subsets with sizes r and n-r. This problem can be visualized as selecting r items from a set of n items without taking order into account, and then the remaining n-r items will form the other subset.

Step 2: Utilize Combinations Formula

To solve this problem, we will use the combinations formula. The number of ways to choose r items from a set of n items (C(n,r)) can be calculated as follows: \( C(n, r) = \frac{n!}{r!(n-r)!} \) Where n! is the factorial of n (the product of all positive integers from 1 to n), and C(n,r) represents the number of ways of selecting a combination of r objects from a set of n objects without taking order into account.

Step 3: Apply the Formula

Now, we will apply the combinations formula to our problem. We are given a set of size n and want to create a subset of size r. So, we can plug n and r into the formula to find the number of ways to create the two disjoint subsets: \( C(n, r) = \frac{n!}{r!(n-r)!} \) So, there are C(n, r) ways to divide the set of size n into two disjoint subsets of sizes r and n-r.

Key Concepts

Disjoint Subsets

When we talk about **disjoint subsets**, we are referring to subsets that have no elements in common. Picture a set of students in a class. If you divide them into two teams for a game, each student should be in only one team. This means the teams are disjoint subsets, as no student is in both teams at the same time.

In the context of combinatorics, if you have a set with a total of \(n\) elements, and you choose \(r\) of them to form one subset, the remaining \(n-r\) elements automatically form the other subset.

Disjoint subsets are essential in problems where we need to partition a set without overlap. Remember, the beauty of disjoint subsets lies in their mutual exclusivity.

Combinations Formula

The **combinations formula** is a critical tool in combinatorics, used to determine the number of ways to select a subset of items from a larger set, without regard to the order of selection.

The formula is expressed as:

• \( C(n, r) = \frac{n!}{r!(n-r)!} \)

This formula tells us how many different ways we can choose \(r\) elements from a total of \(n\).

No matter the order, the focus is solely on the selection.

For instance, if you have 5 different fruits and you want to choose 2 to make a fruit salad, you can use the combinations formula to find out how many different pairings you can make. Remember, combinations are all about selection where order doesn’t matter. They enable solutions to situations where arranging things in a sequence is unnecessary.

Factorial

**Factorial**, represented by an exclamation mark (!), is a simple yet powerful mathematical operation used extensively in permutations, combinations, and probability calculations.

A factorial of a number \(n\), denoted as \(n!\), is the product of all positive integers from 1 to \(n\). For example, 5! is 5 x 4 x 3 x 2 x 1, which equals 120.

The factorial function helps in calculating the number of ways to arrange or select items.

In combinations, it simplifies the process of finding the number of ways to choose a subset of elements from a set where order is not important. Factorials provide crucial support in making sense of complex counting problems in a straightforward manner.

Binomial Coefficient

The **binomial coefficient** is an important concept in the study of combinatorics, denoted as \( C(n, r) \) or sometimes \( \binom{n}{r} \). This coefficient is directly linked with the combinations formula and often appears in the expansion of binomial expressions.

Essentially, the binomial coefficient represents the number of ways to choose \(r\) items from \(n\) items, as given by the formula:

• \( C(n, r) = \frac{n!}{r!(n-r)!} \)

"C" can be thought of standing for "choose," hence the formula calculates how many ways we can "choose" different group arrangements from a larger group. This is particularly useful when determining possible outcomes, such as forming committees or creating groups from larger sets.

Understanding binomial coefficients can simplify much of the complexity in combinatorial mathematics, providing a clear path to solving problems involving selections and grouping without concern for order.