A combination is a mathematical technique for determining the number of possible arrangements in a collection of items where the order of the selection does not matter. It answers the question, "In how many ways can I choose r items from a set of n items?"
For example, if you are choosing 3 toppings for a pizza from a list of 10, the order in which you choose them (e.g., pepperoni then mushrooms then onions) results in the same pizza as choosing them in a different order (e.g., mushrooms then onions then pepperoni). Combinations count these as a single outcome.
| Symbol | Meaning |
|---|---|
| n | The total number of distinct items in the set. |
| r | The number of items to choose from the set. |
| C(n,r) or \( \binom{n}{r} \) | The number of combinations of 'n choose r'. |
| ! | Factorial, the product of all positive integers up to that number (e.g., 4! = 4 × 3 × 2 × 1 = 24). |
This formula calculates the number of ways to choose r items from a set of n items, where order is not important. It is valid for \( 0 \leq r \leq n \).
Imagine a large circle containing 'n' distinct dots, representing the total set of items. A combination is visualized by drawing a smaller circle that encloses 'r' of these dots. There are many such smaller circles possible. The combination formula C(n,r) counts how many unique groups of 'r' dots can be formed, regardless of their position within the smaller circle, emphasizing that order does not matter.
The number of ways to choose r items from n is the same as the number of ways to leave (n-r) items behind.
There is only one way to choose zero items (the empty set) and only one way to choose all n items.
There are n ways to choose one item from a set of n.
The combination formula can be derived from the permutation formula. A permutation is an ordered arrangement.
1. Start with the number of ways to arrange r items chosen from n, which is the permutation formula P(n,r).
2. This counts every different ordering as a separate outcome. For any given set of r items, there are r! ways to arrange them.
3. Since combinations do not care about order, we must divide the total number of permutations by the number of arrangements (r!) for each set of r items to eliminate the overcounting.
4. Substituting the expression for P(n,r) gives the final formula for combinations:
Probability and Statistics: Combinations are fundamental to calculating probabilities. For example, they are used to determine the odds of winning a lottery, the likelihood of being dealt a certain hand in card games (like a full house in poker), and in designing experiments by selecting random samples from a population.
Computer Science: In algorithm design, combinations are used in problems related to selecting subsets, such as finding all possible subsets of a given size. They are also used in cryptography and network security for generating keys and analyzing protocol security.
Genetics: Biologists use combinations to predict the possible genetic makeup of offspring. When parents have different alleles for a trait, combinations can calculate the number of ways these alleles can be passed down.
Quality Control: In manufacturing, a quality control engineer might select a random sample of items from a production batch to test for defects. Combinations are used to determine the number of ways a sample of a certain size can be chosen for inspection.
Choosing a Project Team
A manager needs to select a team of 4 engineers from her department of 15. The combination formula helps determine how many unique team compositions are possible, as the order of selection is irrelevant to the final team.
Restaurant Menu
A restaurant offers a 'build your own' salad with 20 available ingredients, and customers can choose any 5. Combinations are used to calculate the total number of different salad varieties the restaurant can offer.
Lottery Drawings
State and national lotteries involve drawing a set of numbers from a larger pool. The number of possible winning combinations is calculated using C(n,r), which is why the odds of winning are typically very low.
Combinations are a part of a broader field called combinatorics. It's crucial to distinguish them from related concepts based on whether order matters and if repetition is allowed.
| Concept | Order Matters? | Repetition Allowed? | Formula |
|---|---|---|---|
| Combination | No | No | \( \binom{n}{r} = \frac{n!}{r!(n-r)!} \) |
| Permutation | Yes | No | \( P(n,r) = \frac{n!}{(n-r)!} \) |
| Combination with Repetition | No | Yes | \( \binom{n+r-1}{r} \) |
| Permutation with Repetition | Yes | Yes | \( n^r \) |
Confusing Combinations with Permutations: This is the most frequent error. Always ask: 'Does the order of selection matter?' If it doesn't (e.g., selecting a committee), use combinations. If it does (e.g., assigning specific roles like President and VP), use permutations.
Incorrectly Canceling Factorials: Be careful when simplifying the formula. You cannot cancel terms like \( \frac{n!}{r!} \) to get \( (n-r)! \). Always expand the factorials first. For example, \( \frac{10!}{7!} = \frac{10 \times 9 \times 8 \times 7!}{7!} = 10 \times 9 \times 8 \).
Forgetting that \( 0! = 1 \): This is a mathematical convention that is essential for boundary cases. Forgetting this leads to incorrect answers for C(n, n) and C(n, 0), which should both equal 1.