Understanding Permutations and Combinations
Permutations and combinations are fundamental concepts in combinatorics, the branch of mathematics concerned with counting, arrangement, and selection of objects. While both deal with selecting items from a larger set, the key difference lies in whether the order of selection matters.
Key Formulas
Permutation P(n, r)
The number of ways to arrange r items from n items where order matters.
Combination C(n, r)
The number of ways to choose r items from n items where order does not matter.
Factorial n!
The product of all positive integers up to n. By definition, 0! = 1.
Relationship
Permutations always yield a larger or equal result compared to combinations for the same n and r.
Permutations vs Combinations
When to Use Permutations
Use permutations when the order of selection matters. Examples include arranging books on a shelf, determining the number of possible passwords, race finishing orders, or seating arrangements.
When to Use Combinations
Use combinations when the order does not matter. Examples include choosing a committee from a group, selecting lottery numbers, picking a hand of cards, or forming teams.
Practical Examples
- Lock code (Permutation): A 3-digit code from digits 0-9. P(10, 3) = 720 possible codes.
- Lottery (Combination): Choosing 6 numbers from 49. C(49, 6) = 13,983,816 possible combinations.
- Committee (Combination): Choosing 3 members from 10. C(10, 3) = 120 ways.
- Podium finish (Permutation): Top 3 from 8 runners. P(8, 3) = 336 arrangements.
Properties of Combinations
- C(n, 0) = C(n, n) = 1
- C(n, r) = C(n, n - r) (symmetry property)
- C(n, r) = C(n-1, r-1) + C(n-1, r) (Pascal's identity)
- The sum of all C(n, r) for r = 0 to n equals 2^n