Overview
This lecture introduces the concept of combinations (unordered selections) contrasted with permutations (ordered arrangements), and explains the "n choose k" notation used to count ways to select k elements from n without considering order.
Arrangements vs. Selections
- Permutations involve arranging objects in a specific order (order matters).
- Combinations involve selecting objects without regard to order (order does not matter).
- In selection without replacement, once an object is chosen, it cannot be chosen again.
Motivating Example: Forming a Committee
- Given 5 people (Arthur, Bella, Colin, Danielle, Eve), selecting 2 for a committee is a combination problem.
- The order of selection does not matter (Arthur & Bella is the same as Bella & Arthur).
- Listing all combinations for 5 people choosing 2 results in 10 possible committees.
Combination Formula and 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)!], where "!" is the factorial function.
- Example: 5 choose 2 = 5! / (2! × 3!) = 10.
Key Properties of "n Choose k"
- 0 choose 0 = 1, 1 choose 0 = 1, 1 choose 1 = 1 (memorize these).
- n choose 1 = n; n choose n = 1 (useful for quick calculations).
- n choose k = n choose (n - k) (symmetry property).
- For small values, know combinations like 3 choose 2 = 3, 4 choose 2 = 6.
Additional Insights
- "n choose k" can be interpreted as dividing n objects into two groups: one of size k, another of size n - k.
- Recognize that different notations (e.g., 8 choose 3 and 8 choose 5) can represent the same value due to symmetry.
Key Terms & Definitions
- Permutation — Arrangement of objects where order matters.
- Combination — Selection of objects where order does not matter.
- Selection without Replacement — Once chosen, objects are not returned to the pool.
- Factorial (n!) — Product of all positive integers up to n.
- n choose k (C(n, k)) — Number of ways to select k items from n, order not considered.
Action Items / Next Steps
- Memorize key "n choose k" values and properties.
- Practice using the combination formula with small numbers.
- Review factorial calculations for accuracy.