"Introduction to permutations and combinations"

Key Concepts

• Permutations: The arrangement of objects where the order of selection matters.
• Combinations: The selection of objects where the order does not matter.

Sample Question

Suppose we want to choose multiple letters from the letters A, B, C, and D. Consider choosing 2 letters without replacement.

(a) Order Matters

• Definition: When order matters, different arrangements of the same letters are considered distinct.
• Example Strings: AB, AC, AD, BC, BD, CD, BA, CA, DA, CB, DB, DC

Calculation:

• Approach: Use the fundamental counting principle:
  • Choices for the First Letter: 4 (A, B, C, D)
  • Choices for the Second Letter: 3 (since no replacement)
• Total Ways:
  $4 ext{ (first choice)} imes 3 ext{ (second choice)} = 12$

Strings for Order Matters

1. AB
2. AC
3. AD
4. BC
5. BD
6. CD
7. BA
8. CA
9. DA
10. CB
11. DB
12. DC

General Formula for Permutations

• When choosing r objects from n distinct objects:
  P(n, r) = rac{n!}{(n - r)!}

Example for 2 Letters from A, B, C, D:

• P(4, 2) = rac{4!}{(4-2)!} = rac{4 imes 3 imes 2 imes 1}{2 imes 1} = 12

(b) Order Does Not Matter

• Definition: When order does not matter, the same letters arranged differently are considered identical.
• Identical Strings: Each column in the choices from (a) contains essentially the same pairs, e.g. AB and BA.

Calculation:

• Combine & Eliminate Duplicates:

  • From earlier, we see 12 arrangements but need to account for duplicates.
  • Each pair can be arranged in $2!$ ways.

• Total Ways:
  C(n, r) = rac{P(n, r)}{r!}

• For 2 letters:
  C(4, 2) = rac{P(4, 2)}{2!} = rac{12}{2} = 6

General Formula for Combinations

• When choosing r objects from n distinct objects:
  C(n, r) = rac{n!}{r!(n - r)!}

Example for 2 Letters from A, B, C, D:

• C(4, 2) = rac{4!}{2! imes (4-2)!} = rac{24}{2 imes 2} = 6

Summary of Results

• Ways if Order Matters: 12 ways
• Ways if Order Does Not Matter: 6 ways