Permutations and Combinations
"Counting is the most basic mathematical operation. But counting POSSIBILITIES requires the tools in this chapter."
1. Chapter Overview
How many ways can things be arranged or selected? This chapter provides the systematic tools: the Fundamental Principle of Counting, Factorial notation (n!), Permutations (arrangements — order matters: nPr), and Combinations (selections — order doesn't matter: nCr). These form the basis of PROBABILITY (next chapter).
2. Fundamental Principle of Counting (Multiplication Principle)
- If one event can occur in m ways, and (for each of these m ways) another event can occur in n ways → the two events TOGETHER can occur in m × n ways
- This extends to any number of events: m₁ × m₂ × m₃ × ...
Example
- A restaurant has 3 starters and 4 main courses.
- A customer wants 1 starter AND 1 main course.
- Total combinations: 3 × 4 = 12 possible meals.
3. Factorial Notation — n!
- n! = n × (n-1) × (n-2) × ... × 3 × 2 × 1
- 0! = 1 (by convention — makes the formulas work)
- 5! = 5 × 4 × 3 × 2 × 1 = 120
- n! = n × (n-1)!
4. Permutations (nPr) — Order MATTERS
Definition
- The number of ways to ARRANGE r objects selected from n distinct objects, where ORDER MATTERS
- nPr = n! / (n — r)!
Special Cases
- Arranging ALL n objects: nPn = n! (no restriction)
- Arranging n objects where some are IDENTICAL: n! / (p₁! p₂! ... pₖ!) where p₁, p₂ are the counts of each type of identical object
Key Principle: Multiply choices
- Arranging 3 letters from {A, B, C, D, E}: 5 × 4 × 3 = 60 = ⁵P₃
- First position: 5 choices. Second: 4 remaining. Third: 3 remaining.
5. Combinations (nCr) — Order DOES NOT MATTER
Definition
- The number of ways to SELECT r objects from n distinct objects, where ORDER DOES NOT MATTER
- nCr = n! / [r! (n — r)!]
- nCr = nPr / r! (take the permutations and divide by the number of ways to rearrange the r selected objects)
- Also written as C(n, r) or (ⁿᵣ)
Key Properties
- nCr = nC(n-r). Choosing r objects is THE SAME as choosing the n-r objects to LEAVE OUT.
- nC₀ = nCn = 1
- nC₁ = n
- nCr + nC(r+1) = (n+1)C(r+1)
6. Difference Between Permutations and Combinations
| Permutations (nPr) | Combinations (nCr) | |
|---|---|---|
| Order? | ORDER MATTERS (ABC ≠ CBA) | Order DOES NOT MATTER (ABC = CBA) |
| What it counts | ARRANGEMENTS | SELECTIONS |
| Formula | n!/(n-r)! | n!/[r!(n-r)!] |
| Value | nPr ≥ nCr (larger or equal) | nCr ≤ nPr |
| When to use | Forming numbers, words. Seating arrangements. President/VP/Secretary. | Choosing a team. Selecting a committee. |
7. Exam Focus
- Fundamental Principle of Counting (multiplication principle)
- n! — factorial definition, 0! = 1
- nPr — formula, when to use (order matters)
- nCr — formula, properties (nCr = nC(n-r))
- Distinguishing permutations from combinations — KEY SKILL
8. Key Formulas
- nPr = n! / (n-r)!
- nCr = n! / [r! (n-r)!]
- nCr = nC(n-r)
- nCr = nPr / r!
- Arranging n objects with p identical of one type, q of another: n!/(p! q!)
9. Conclusion
Counting possibilities is systematic — not guesswork:
- PRINCIPLE OF COUNTING: Multiply the number of choices at each step
- PERMUTATIONS (nPr): Arrangements. Order matters. President, VP, Secretary — who gets which office MATTERS.
- COMBINATIONS (nCr): Selections. Order doesn't matter. Choosing a committee — the COMMITTEE is the same regardless of the order in which members were chosen.
The difference between permutations and combinations is one word: ORDER. If you're making a queue → permutations. If you're picking a team → combinations.
