Problem 50 - Algebra for College Students

Question

Compute \(C(7,3)\) and \(C(7,4)\). Compute \(C(8,2)\) and \(C(8,6)\). Compute \(C(9,8)\) and \(C(9,1)\). Now argue that \(C(n, r)=C(n, n-r)\) for \(r \leq n\).

Step-by-Step Solution

Answer

Binomial coefficients are symmetric, so \( C(n, r) = C(n, n-r) \).

Step 1: Understand the Binomial Coefficient

The binomial coefficient, also known as a combination, is used to determine the number of ways to choose a subset of elements from a set, without regard to the order of elements. It is denoted as \( C(n, r) \) where \( n \) is the total number of elements and \( r \) is the number of elements to choose. The formula to calculate \( C(n, r) \) is \( C(n, r) = \frac{n!}{r!(n-r)!} \) where \(!\) denotes factorial.

Step 2: Compute \( C(7, 3) \) and \( C(7, 4) \)

Using the formula \( C(n, r) = \frac{n!}{r!(n-r)!} \):For \( C(7, 3) \):\[C(7, 3) = \frac{7!}{3!4!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35\]For \( C(7, 4) \):\[C(7, 4) = \frac{7!}{4!3!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35\]Notice how both yield the same result.

Step 3: Compute \( C(8, 2) \) and \( C(8, 6) \)

For \( C(8, 2) \):\[C(8, 2) = \frac{8!}{2!6!} = \frac{8 \times 7}{2 \times 1} = 28\]For \( C(8, 6) \):\[C(8, 6) = \frac{8!}{6!2!} = \frac{8 \times 7}{2 \times 1} = 28\]These computations show they equal as well.

Step 4: Compute \( C(9, 8) \) and \( C(9, 1) \)

For \( C(9, 8) \):\[C(9, 8) = \frac{9!}{8!1!} = 9\]For \( C(9, 1) \):\[C(9, 1) = \frac{9!}{1!8!} = 9\]Again, both results match each other.

Step 5: General Argument for \( C(n, r) = C(n, n-r) \)

The symmetry in binomial coefficients comes from their definition \( C(n, r) = \frac{n!}{r!(n-r)!} \). Observing this formula, if we swap \( r \) with \( n-r \), we have \( C(n, n-r) = \frac{n!}{(n-r)!r!} \), which is clearly equal to \( C(n, r) \). Thus, \( C(n, r) = C(n, n-r) \). This symmetry means the number of ways to choose \( r \) elements is the same as choosing \( n-r \) elements.

Key Concepts

Combinations

Combinations are a fundamental concept in mathematics and are used to find out the number of ways to choose items from a larger set. Unlike permutations, combinations do not consider the order of the items. This is particularly useful in situations where the sequence does not matter, such as choosing team members or lottery numbers.
To calculate the number of combinations, we use the binomial coefficient, denoted as \( C(n, r) \), which gives the number of ways to choose \( r \) elements from a set of \( n \) elements without regard to order. The general formula for combinations is:

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

Here, "\(!\)" denotes a factorial, which is a core concept in calculating combinations.

Factorials

Factorials play an essential role in calculating combinations, as they denote the product of all positive integers up to a certain number. For example, the factorial of 4, denoted as \(4!\), is the product \( 4 \times 3 \times 2 \times 1 = 24 \).
In the context of combinations, factorials allow for simplifying the number of different ways items can be arranged. By using the formula for combinations, \( C(n, r) = \frac{n!}{r!(n-r)!} \), factorials make it possible to calculate large combinations easily:

• The \( n! \) accounts for the total arrangements of \( n \) items.
• The \( r! \) and \( (n-r)! \) terms cancel out the repetitive arrangements, leaving only the unique combinations.

Understanding how factorials work is key to mastering combinations and permutations alike.

Symmetry in Combinations

One fascinating aspect of combinations is their inherent symmetry, shown by the fact that \( C(n, r) = C(n, n-r) \). This symmetry means that choosing \( r \) items from \( n \) elements is equivalent to choosing \( n-r \) elements to leave out.
For example, when selecting a committee of 3 people from a group of 7, it's the same as deciding which 4 people will not be part of the committee; both calculations yield the same number of combinations.
To understand this symmetry in mathematical terms:

• The formula \( C(n, r) = \frac{n!}{r!(n-r)!} \) simplifies to the same result when you switch \( r \) with \( n-r \).
• This highlights the reciprocal nature of choosing versus not choosing elements from a set.

This symmetry can simplify calculations and provide insights into different counting methods.

Binomial Theorem

The Binomial Theorem is an elegant mathematical principle that connects algebra to combinatorics and provides a way to expand expressions in powers of a binomial, \((a + b)^n\). Each term in this expansion can be represented using binomial coefficients.
The theorem states that:

• \((a + b)^n = \sum_{r=0}^{n} C(n, r) a^{n-r}b^r\)

Here, each coefficient \( C(n, r) \) reflects the number of ways to choose \( r \) items from \( n \), linking the theorem directly to combinations.
This theorem has vast applications, from solving algebraic equations to determining probabilities in different fields. It's a universal tool in mathematics that provides a systematic way of working with powers of sums.