Chapter 16: Permutations & Combinations Core Concepts

Chapter 16: Permutations & Combinations Core Concepts

Introduction to Counting Problems

  • Everyday counting problems include arrangements, partitions, and distributions.
  • Key questions examples:
    • How many different 4-digit numbers using the digits 1, 2, 3, 4, 5 without repetition?
    • How many ways to select 4 representatives from 10 students?
    • How to arrange 25 students in a row?

Principles of Counting

Mutually Exclusive Occurrences
  • Definition: Two events cannot happen at the same time.
  • Example: Rolling a die can result in either even or odd numbers (mutually exclusive).
The Addition Principle
  • If one event can happen in n ways and another in m ways, then the total is n + m.
  • Generalization for k events:
    • Total ways = n1 + n2 + … + nk
  • Example: Mail delivery from Singapore to Tokyo via 4 airlines and 3 shipping lines = 4 + 3 = 7 ways.
Independent Occurrences
  • Definition: If the occurrence of one event does not affect another.
  • Example: Tossing a coin and rolling a die.
The Multiplication Principle
  • If one event can occur in n ways and another in m ways, then both can occur in n × m ways.
  • Generalization for k independent events:
    • Total ways = n1 × n2 × … × nk
  • Example: 2 buses to Pasir Ris Central and 3 buses to TMJC give 2 × 3 = 6 ways.

Combinations

  • Definition: Selection of objects where order does not matter.
  • Notations:
    • nCr: Number of combinations of r from n.
  • Formula: nCr Formula
    • Remarks: nCr = n! / (r! * (n-r)!)
Examples of Combinations
  • Choose 3 from 5 integers: {1, 2, 3, 4, 5}.
  • Form committees: 3 from 10 people.
Calculating Combinations
  • 0! = 1 for consistency in formulas.
  • Using graphing calculators: Effective for calculating combinations such as 6C3.

Permutations

  • Definition: Arrangement of objects in a specific order.
  • Types:
    • n!: Arranging n distinct objects.
    • nPr: Arranging r from n distinct.
  • Formula: nPr = n! / (n - r)!
Examples of Permutations
  • Arranging letters: Total arrangements of "EQUATIONS" = 9!.
  • Circular Permutations: n distinct objects in a circle have (n - 1)! arrangements.

Counting with Restrictions

  • Some problems involve arrangements under conditions.
  • Use grouping or slotting methods to satisfy conditions.
  • Example: Arrange 4 boys and 2 girls if girls must sit next to each other.
    • Treating girls as one unit gives total arrangements = 5! for units and 2! for girls.
Summary of Techniques
  • Splitting into cases.
  • Positional restrictions or constraints.
  • Grouping when items need to be together.
  • Slotting for separation conditions.
  • Taking complements for counting exclusions.

Key Concept Relationships

  • Addition Principle: Mutually exclusive events.
  • Multiplication Principle: Independent events.
  • Distinguish combination vs permutation importance based on order consideration.
Practice Problems and Exercises
  • Included real-exam-like questions focused on applications of permutations and combinations principles.
  • Encourage group discussions for solving problems collaboratively to enhance understanding.
Additional Problem Examples
  • How many 4-letter codes can be formed with specific conditions?
  • Counting arrangements with identical items or restrictions.

Conclusion

  • Mastery of permutations and combinations requires practice through diverse problem-solving scenarios.