Combinations are a fundamental concept in discrete mathematics, particularly in the study of combinatorics, which is concerned with counting, arranging, and selecting objects.

Combinations

A combination refers to the selection of items from a larger set where the order of selection does not matter. For example, choosing 2 books from a set of 5 books is a combination, not a permutation, because the order in which the books are chosen does not matter.

Combination Formula

The number of ways to select $r$ elements from a set of $n$ elements (denoted as $\binom{n}{r}$ or "n choose r") is given by the combination formula:

$\binom{n}{r} = \frac{n!}{r!(n-r)!}$

Where:

• $n!$ (n factorial) is the product of all positive integers up to $n$.
• $r!$ (r factorial) is the product of all positive integers up to $r$.
• $(n - r)!$ is the factorial of the difference between the total elements and the selected elements.

Explanation

• $n$ is the total number of items in the set.
• $r$ is the number of items you want to select.
• The formula counts all possible selections of $r$ items from $n$, without regard to the order.

Example

Suppose we have a set of 5 elements: $\{A, B, C, D, E\}$ and we want to select 3 elements from this set. Using the combination formula:

$\binom{5}{3} = \frac{5!}{3!(5-3)!} = \frac{5!}{3!2!} = \frac{5 \times 4 \times 3!}{3! \times 2 \times 1} = \frac{20}{2} = 10$

So, there are 10 different ways to choose 3 elements from 5.

The possible combinations are: $\{A, B, C\}, \{A, B, D\}, \{A, B, E\}, \{A, C, D\}, \{A, C, E\}, \{A, D, E\}, \{B, C, D\}, \{B, C, E\}, \{B, D, E\}, \{C, D, E\}$

Key Points

• Combinations do not consider the order of selection. For example, choosing $A, B$ is the same as choosing $B, A$.
• Permutations, on the other hand, do consider the order of selection.

Related Topics in Discrete Structures

1. Permutations: Arrangements where the order matters.
2. Binomial Theorem: Expands expressions of the form $(a + b)^n$, which involves combinations.
3. Pascal’s Triangle: A triangular array of binomial coefficients that can be used to compute combinations.
4. Multiset Combinations: When repetition is allowed in selection.
5. Pigeonhole Principle: Used in combinatorial proofs and counting.

Tip:

To simplify factorials in combination formulas, cancel out common terms in both the numerator and the denominator. For instance, in $\binom{n}{r} = \frac{n!}{r!(n - r)!}$, $n! = n \times (n-1) \times (n-2) \times \dots \times (n-r+1) \times r!$, so you can cancel the $r!$ terms to avoid dealing with large factorials.

---

Do you want more details on any specific concept or example related to combinations, or have any questions on other discrete structures topics?

Here are some related questions:

1. How do permutations differ from combinations in counting problems?
2. What is the Binomial Theorem and how does it relate to combinations?
3. Can you provide an example involving the use of combinations with repetition?
4. How can Pascal’s Triangle be used to quickly calculate combinations?
5. What is the inclusion-exclusion principle in combinatorics?

Tip: When you're calculating combinations, it's helpful to remember that symmetry exists: $\binom{n}{r} = \binom{n}{n-r}$.