Permutations and Combinations
6.1 Introduction
Permutations and combinations are fundamental concepts in counting and probability that deal with arrangements and selections of objects.
Key Differences:
- Permutations consider order of arrangement
- Combinations do not consider order
Applications: Probability, statistics, cryptography, and decision making.
6.2 Fundamental Principle of Counting
Also known as the Multiplication Principle:
If one event can occur in m ways and a second can occur independently in n ways, then the two events can occur in m × n ways.
Example:
If you have 3 shirts and 4 pants, you can create 3 × 4 = 12 different outfits.
Extended Principle: For k events with n₁, n₂,..., nₖ ways respectively, the total number of ways is n₁ × n₂ × ... × nₖ.
6.3 Permutations
Arrangements of objects where order matters.
Permutations of n distinct objects:
n! = n × (n-1) × ... × 2 × 1
(n factorial)
Permutations of n objects taken r at a time:
nPr = n!/(n-r)!
Permutations with repeated elements:
n!/(n₁! × n₂! × ... × nₖ!)
where n₁, n₂,..., nₖ are counts of identical objects
Examples:
1. Arranging 3 books (A, B, C): 3! = 6 permutations
2. Selecting president and vice-president from 10 people: 10P2 = 90 ways
3. Arranging letters in "MISSISSIPPI": 11!/(4!×4!×2!) = 34,650 ways
6.4 Combinations
Selections of objects where order doesn't matter.
Combinations of n objects taken r at a time:
nCr = n!/(r!(n-r)!)
Also written as C(n,r) or (n choose r)
Key Properties:
- nCr = nC(n-r) (symmetry)
- nCr + nC(r+1) = (n+1)C(r+1) (Pascal's identity)
- nC0 + nC1 + ... + nCn = 2ⁿ
| Scenario | Permutation (P) | Combination (C) |
|---|---|---|
| Password | Yes (order matters) | No |
| Committee selection | No | Yes (order irrelevant) |
| Podium positions | Yes (1st, 2nd, 3rd) | No |
Examples:
1. Choosing 3 toppings from 10 available: 10C3 = 120 combinations
2. Selecting 5 cards from a deck of 52: 52C5 = 2,598,960 poker hands
3. Forming a 4-member team from 7 people: 7C4 = 35 ways
Special Cases and Relationships:
- nPr = nCr × r! (permutations are combinations with ordered arrangements)
- With repetition: n^r (permutations), (n+r-1)Cr (combinations)
- Circular permutations: (n-1)!
Practice Problem:
A pizza place offers 8 toppings. How many different pizzas can be made with:
a) Exactly 3 toppings? 8C3 = 56
b) At most 3 toppings? 8C0 + 8C1 + 8C2 + 8C3 = 1 + 8 + 28 + 56 = 93
Applications:
- Lottery probability calculations
- Experimental design in statistics
- Cryptographic key combinations
- Bioinformatics (DNA sequence analysis)