Understanding Combination

In mathematics, a combination refers to the selection of items from a larger set such that the order of selection does not matter. This is different from a permutation, where order is important.

For example, if you have three fruits: apple, banana, and cherry, the combinations of two fruits are {apple, banana}, {apple, cherry}, and {banana, cherry}. Notice that {apple, banana} is the same as {banana, apple} in combinations.

Notation and Definition

The number of ways to choose \( r \) objects from \( n \) distinct objects without regard to order is denoted by:

This is read as "n choose r" and is called a combination.

Combination Formula

The formula to calculate combinations is:

where \( n! \) (n factorial) is the product of all positive integers up to \( n \), and \( 0! = 1 \) by definition.

Difference Between Permutation and Combination

Properties of Combinations

• Symmetry: \( \binom{n}{r} = \binom{n}{n-r} \). Choosing \( r \) items is the same as excluding \( n-r \) items.
• Sum of combinations: \( \sum_{r=0}^n \binom{n}{r} = 2^n \). This represents the total number of subsets of an \( n \)-element set.
• Pascal's Identity: \( \binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r} \).

Relation Between Permutations and Combinations

The number of permutations of \( r \) objects chosen from \( n \) is related to combinations by:

This is because permutations count all ordered arrangements, while combinations count unordered selections.

Connection to Set Theory

Combination theory is closely linked to sets and subsets. The number of subsets of size \( r \) from a set of size \( n \) is exactly \( \binom{n}{r} \). The power set of a set \( S \) is the set of all subsets of \( S \), and its cardinality is \( 2^n \) if \( n = |S| \).

For example, if \( S = {1, 2, 3} \), then the power set \( \mathcal{P}(S) \) has \( 2^3 = 8 \) subsets:

Real-world Examples

• Committee Selection: Choosing 3 students out of 10 for a committee.
• Lottery: Selecting 6 numbers out of 49 without order.
• Card Games: Number of 5-card hands from a 52-card deck.

Common Mistakes to Avoid

• Confusing permutations with combinations (order matters vs order does not matter).
• Incorrect factorial calculations or forgetting \( 0! = 1 \).
• Using combination formula when repetition is allowed (which requires a different formula).

Pascal's Triangle (first 6 rows):          1         1 1        1 2 1       1 3 3 1      1 4 6 4 1     1 5 10 10 5 1Note: Each number is \( \binom{n}{r} \).

Summary

Combinations are fundamental in counting problems where order does not matter. They are widely used in probability, statistics, and various fields of mathematics. Understanding the difference between permutations and combinations, and mastering the formula and properties, is essential for solving entrance exam problems efficiently.

Worked Examples

Formula Bank

• Combination Formula: \( \displaystyle \binom{n}{r} = \frac{n!}{r!(n-r)!} \)
• Permutation Formula: \( \displaystyle ^nP_r = \frac{n!}{(n-r)!} \)
• Relation between Permutation and Combination: \( ^nP_r = \binom{n}{r} \times r! \)
• Number of subsets of size \( r \) from set of size \( n \): \( \binom{n}{r} \)
• Total number of subsets (power set cardinality): \( 2^n \)
• Pascal's Identity: \( \binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r} \)
• Set Union-Intersection Formula: \( n(A \cup B) = n(A) + n(B) - n(A \cap B) \)