Overview
This lecture introduces combinations (selection without replacement), explains how they differ from permutations, and details the use and properties of "n choose k" notation (binomial coefficients).
Recap: Permutations (Order Matters)
- Permutations count arrangements where the order is important (e.g., ranking runners in a race).
- In permutations, choosing A then B is different from choosing B then A.
Combinations: Selection Without Replacement
- Combinations focus on selecting items where order does not matter.
- Example: Choosing books to read or forming a committee—only the final group matters, not the order of selection.
- Selection occurs without replacement: once an item is chosen, it cannot be selected again.
Example: Committee Formation
- Given 5 people, the task is to choose 2 for a committee.
- Choosing Arthur and Bella is the same as choosing Bella and Arthur.
- Listing all possibilities for 5 people choosing 2 gives 10 unique committees.
General Formula and Choose Notation
- The number of ways to select K objects from N is denoted as "n choose k" or C(n, k).
- Formula: n choose k = n! / (k! × (n−k)!)
- Example: 5 choose 2 = 10.
Important Choose Notation Values and Properties
- 0 choose 0 = 1; 1 choose 0 = 1; 1 choose 1 = 1.
- n choose 0 = 1 (one way to choose nothing); n choose n = 1 (one way to choose everything).
- n choose 1 = n (one way to choose each item).
- n choose k = n choose n−k (symmetry property).
- Example: 5 choose 2 = 5 choose 3 = 10.
Connections and Applications
- Choose notation can also represent splitting a set into two groups: chosen and not chosen.
- Useful for counting problems and appears throughout probability and combinatorics.
Key Terms & Definitions
- Permutation — an arrangement of items where order matters.
- Combination — a selection of items where order does not matter.
- Without replacement — once chosen, an item cannot be selected again.
- n choose k / Binomial Coefficient — number of ways to choose k items from n, written as n!/(k!(n−k)!).
Action Items / Next Steps
- Memorize key choose notation values and properties.
- Practice computing combinations using the formula.
- Prepare to use combinations in future counting and probability problems.