Permutations and Combinations

COMPREHENSIVE CHAPTER NOTES: PERMUTATIONS AND COMBINATIONS

FUNDAMENTAL PRINCIPLE OF COUNTING

**Definition:** The Fundamental Principle of Counting (also called the Multiplication Principle) states that if an event can occur in m different ways, and following this, another event can occur in n different ways, then the total number of occurrences of both events in the given order is **m × n**.

**General Extension:** For k successive events occurring in m₁, m₂, m₃, ..., mₖ ways respectively, the total number of ways = **m₁ × m₂ × m₃ × ... × mₖ**

**Key Points:**

The principle applies when events occur **in a definite order**

Each way of the first event can be paired with every way of the second event

Order of events matters and must be predetermined

The principle is fundamental to all counting problems

**Worked Example 1:**

A person has 5 shirts, 4 pairs of trousers, and 2 pairs of shoes. In how many ways can they dress up?

Shirt can be chosen: 5 ways

Trousers can be chosen: 4 ways

Shoes can be chosen: 2 ways

By multiplication principle: 5 × 4 × 2 = **40 ways**

**Worked Example 2:**

How many 3-digit numbers can be formed using digits 1, 2, 3, 4, 5 if repetition is allowed?

First digit (hundreds place): 5 ways

Second digit (tens place): 5 ways (repetition allowed)

Third digit (units place): 5 ways

Total = 5 × 5 × 5 = **125 numbers**

**Important Exam Technique:** When forming numbers with restrictions (like even numbers, numbers starting with specific digit), identify which position has restrictions and fill that position first.

---

FACTORIAL NOTATION

**Definition:** The factorial of a natural number n, denoted **n!**, is the product of all natural numbers from 1 to n.

**n! = n × (n-1) × (n-2) × ... × 3 × 2 × 1**

**Special Case:** **0! = 1** (by definition; this is essential for permutation formulas)

**Factorial Values (for reference):**

1! = 1

2! = 2

3! = 6

4! = 24

5! = 120

6! = 720

7! = 5040

10! = 3,628,800

**Recursive Formula:** **n! = n × (n-1)!** for n ≥ 1

**Properties:**

n! grows extremely rapidly

We can express: n! = n × (n-1) × (n-2) × ... × (n-r+1) × (n-r)!

Useful for simplification: **n!/(n-r)! = n × (n-1) × (n-2) × ... × (n-r+1)**

**Worked Example:**

Evaluate 8!/6!:

8!/6! = (8 × 7 × 6!)/6! = 8 × 7 = **56**

Evaluate 10!/(10-3)!:

10!/7! = (10 × 9 × 8 × 7!)/7! = 10 × 9 × 8 = **720**

**Exam Tip:** Always simplify factorial expressions before calculating; never compute complete factorials for large numbers.

---

PERMUTATIONS

**Definition:** A **permutation** is an arrangement of objects in a definite order where the order of arrangement matters. Different orderings of the same objects are considered different permutations.

**Key Distinction:** Permutations are arrangements (order-sensitive); combinations are selections (order-insensitive).

**Real-life Examples:**

Arranging students in a line (order matters)

Arranging books on a shelf

Password combinations with distinct characters

Finishing order in a race

PERMUTATIONS OF n DISTINCT OBJECTS TAKEN r AT A TIME (r ≤ n, NO REPETITION)

**Theorem (nPr Formula):**

The number of permutations of n different objects taken r at a time is:

**ⁿPᵣ = n!/(n-r)!**

where **0 ≤ r ≤ n**

**Derivation:** When arranging r objects from n distinct objects:

1st position: n choices

2nd position: (n-1) choices

3rd position: (n-2) choices

...

rth position: (n-r+1) choices

By multiplication principle: ⁿPᵣ = n(n-1)(n-2)...(n-r+1)

Multiplying numerator and denominator by (n-r)!:

ⁿPᵣ = [n(n-1)(n-2)...(n-r+1) × (n-r)!] / (n-r)! = **n!/(n-r)!**

**Special Cases:**

**ⁿPₙ = n!** (arranging all n objects)

**ⁿP₀ = 1** (one way to arrange zero objects — do nothing)

**ⁿP₁ = n** (n ways to select and arrange 1 object)

**Worked Example 1:**

Find 6P₃:

⁶P₃ = 6!/(6-3)! = 6!/3! = (6 × 5 × 4 × 3!)/(3!) = 6 × 5 × 4 = **120**

**Worked Example 2:**

In how many ways can a President, Vice-President, and Secretary be chosen from 10 people?

This is selecting 3 people from 10 where order matters

Number of ways = ¹⁰P₃ = 10!/(10-3)! = 10!/7! = 10 × 9 × 8 = **720**

**Worked Example 3:**

How many 4-digit numbers can be formed from digits 1, 2, 3, 4, 5, 6, 7 (no repetition)?

Number of ways = ⁷P₄ = 7!/(7-4)! = 7!/3! = 7 × 6 × 5 × 4 = **840**

---

PERMUTATIONS WITH REPETITION ALLOWED

**Theorem:** The number of permutations of n objects taken r at a time, where repetition is allowed, is **nʳ**.

**Derivation:**

Each of r positions can be filled independently

Each position has n choices

Total ways = n × n × n × ... (r times) = **nʳ**

**Worked Example:**

How many 3-digit numbers can be formed using digits 0-9 (repetition allowed)?

Each of 3 positions can use any of 10 digits

Total = 10 × 10 × 10 = **1000**

However, for valid 3-digit numbers (not starting with 0):

First digit: 9 choices (1-9)

Second digit: 10 choices (0-9)

Third digit: 10 choices (0-9)

Total = 9 × 10 × 10 = **900**

---

PERMUTATIONS OF OBJECTS WHEN ALL ARE NOT DISTINCT

**Theorem:** When n objects have p identical objects of one kind, p₁ identical objects of another kind, p₂ of another kind, etc., the number of distinct permutations is:

**n! / (p₁! × p₂! × p₃! × ... × pₖ!)**

where p₁ + p₂ + ... + pₖ ≤ n

**Explanation:** If all objects were distinct, there would be n! arrangements. But identical objects create overcounting: each distinct arrangement is counted p₁! × p₂! × ... times (once for each arrangement of identical objects among themselves).

**Worked Example 1:**

Find the number of distinct permutations of the letters in BANANA:

Total letters: 6

Identical letters: 3 A's, 2 N's

Number of arrangements = 6!/(3! × 2!) = 720/(6 × 2) = 720/12 = **60**

**Worked Example 2:**

Arrange the letters of MISSISSIPPI:

Total letters: 11

M appears: 1 time

I appears: 4 times

S appears: 4 times

P appears: 2 times

Number of arrangements = 11!/(1! × 4! × 4! × 2!) = 39,916,800/(24 × 24 × 2) = **34,650**

**Worked Example 3:**

How many signals can be made using 3 red flags, 2 blue flags, and 1 green flag?

Total flags: 6

Identical red flags: 3

Identical blue flags: 2

Green flags: 1

Signals = 6!/(3! × 2! × 1!) = 720/(6 × 2 × 1) = **60**

---

SOLVING EQUATIONS INVOLVING PERMUTATIONS

**Strategy:** Express ⁿPᵣ using the factorial formula and simplify before solving.

**Worked Example 1:**

Find n if ⁿP₂ = 42:

ⁿP₂ = n!/(n-2)! = n(n-1) = 42

n² - n - 42 = 0

(n-7)(n+6) = 0

n = 7 (since n must be positive)

**Worked Example 2:**

Find n if ⁿP₃ = 10 × ⁿ⁻¹P₂:

n!/(n-3)! = 10 × (n-1)!/(n-3)!

n(n-1)(n-2)(n-3)! / (n-3)! = 10 × (n-1)(n-2)(n-3)! / (n-3)!

n(n-1)(n-2) = 10(n-1)(n-2)

n = 10 (dividing by (n-1)(n-2) when n > 2)

---

COMBINATIONS

**Definition:** A **combination** is a selection of objects where **order does NOT matter**. Different orderings of the same selection are considered the same combination.

**Key Distinction from Permutations:**

Permutation: AB and BA are different (arrangement matters)

Combination: {A,B} and {B,A} are the same (only selection matters)

**Real-life Examples:**

Selecting committee members (order doesn't matter)

Choosing toppings for pizza

Selecting fruits from a basket

Choosing questions to answer in an exam

COMBINATIONS OF n DISTINCT OBJECTS TAKEN r AT A TIME

**Theorem (ⁿCᵣ Formula):**

The number of combinations of n distinct objects taken r at a time is:

**ⁿCᵣ = n! / (r!(n-r)!) = ⁿPᵣ / r!**

where **0 ≤ r ≤ n**

**Derivation:**

The number of permutations of r objects from n objects is ⁿPᵣ

Among these ⁿPᵣ permutations, each set of r objects is counted r! times (once for each arrangement of r objects)

Therefore: ⁿCᵣ = ⁿPᵣ / r! = [n!/(n-r)!] / r! = **n! / (r!(n-r)!)**

**Alternative Formula:** ⁿCᵣ = n(n-1)(n-2)...(n-r+1) / r!

**Special Cases:**

**ⁿC₀ = 1** (one way to select nothing)

**ⁿCₙ = 1** (one way to select everything)

**ⁿC₁ = n** (n ways to select 1 object)

**ⁿCᵣ = ⁿC₍ₙ₋ᵣ₎** (complementary combinations)

**Symmetry Property:** ⁿCᵣ = ⁿC₍ₙ₋ᵣ₎

**Proof:** ⁿC₍ₙ₋ᵣ₎ = n! / [(n-r)!(n-(n-r))!] = n! / [(n-r)!r!] = ⁿCᵣ ✓

**Worked Example 1:**

Find ⁶C₃:

⁶C₃ = 6! / (3! × 3!) = (6 × 5 × 4) / (3 × 2 × 1) = 120/6 = **20**

**Worked Example 2:**

A committee of 5 people is to be chosen from 12 people. How many ways?

Order doesn't matter (only selection)

Number of ways = ¹²C₅ = 12! / (5! × 7!)

= (12 × 11 × 10 × 9 × 8) / (5 × 4 × 3 × 2 × 1)

= 95,040 / 120 = **792**

**Worked Example 3:**

From 8 red balls and 5 blue balls, select 3 red and 2 blue. How many ways?

Ways to select 3 red from 8: ⁸C₃ = 56

Ways to select 2 blue from 5: ⁵C₂ = 10

Total ways = 56 × 10 = **560** (using multiplication principle)

---

RELATIONSHIP BETWEEN PERMUTATIONS AND COMBINATIONS

**Fundamental Relationship:**

**ⁿPᵣ = ⁿCᵣ × r!**

This shows that permutations = combinations × arrangements of selected objects

**Interpretation:**

First, select r objects from n: ⁿCᵣ ways

Then, arrange these r objects: r! ways

Total permutations: ⁿCᵣ × r!

**Practical Example:**

Selecting 3 people from 10 for a committee: ¹⁰C₃ = 120

Selecting 3 people from 10 for President, VP, Secretary: ¹⁰P₃ = 720

Relationship: ¹⁰P₃ = ¹⁰C₃ × 3! = 120 × 6 = 720 ✓

---

IMPORTANT FORMULAS AND PROPERTIES

**Pascal's Identity (Combination Property):**

**ⁿCᵣ + ⁿC₍ᵣ₋₁₎ = ⁿ⁺¹Cᵣ**

**Proof:**

ⁿCᵣ + ⁿC₍ᵣ₋₁₎ = n!/(r!(n-r)!) + n!/((r-1)!(n-r+1)!)

= [n!(n-r+1) + n! × r] / (r!(n-r+1)!)

= n![(n-r+1) + r] / (r!(n-r+1)!)

= n!(n+1) / (r!(n-r+1)!)

= **(n+1)! / (r!(n+1-r)!) = ⁿ⁺¹Cᵣ** ✓

**Sum of Combinations:**

**ⁿC₀ + ⁿC₁ + ⁿC₂ + ... + ⁿCₙ = 2ⁿ**

(Total number of subsets of a set with n elements)

---

WORKED EXAMPLES (COMPREHENSIVE)

**Problem 1:** How many ways can 5 red balls, 3 blue balls, and 2 green balls be arranged in a line?

Total objects: 10

Identical red: 5, Identical blue: 3, Identical green: 2

Arrangements = 10! / (5! × 3! × 2!) = 3,628,800 / (120 × 6 × 2) = **2,520**

**Problem 2:** From 5 men and 4 women, how many committees of 3 members can be formed such that there is at least 1 woman?

Total committees with at least 1 woman = Total committees - Committees with no women

Total 3-member committees from 9 people: ⁹C₃ = 84

Committees with no women (all men): ⁵C₃ = 10

Committees with at least 1 woman = 84 - 10 = **74**

**Problem 3:** How many words can be formed by rearranging the letters of ALLOY such that vowels are together?

Letters: A, L, L, O, Y (L repeats)

Vowels: A, O (treat as single unit)

Objects to arrange: (AO), L, L, Y = 4 objects with 2 L's identical

Arrangements = 4! / 2! = 24/2 = **12**

Vowels A, O can be arranged among themselves in 2! = 2 ways

Total = 12 × 2 = **24**

**Problem 4:** Find the number of 4-digit numbers using 1, 2, 3, 4, 5, 6 where the number is even and repetition not allowed.

Even numbers end in 2, 4, or 6

Last digit: 3 choices (2, 4, or 6)

Remaining 3 digits from remaining 5 digits: ⁵P₃ = 5 × 4 × 3 = 60

Total = 3 × 60 = **180**

---

KEY EXAM STRATEGIES

**Identifying When to Use Permutations vs Combinations:**

**Use Permutations (ⁿPᵣ):** When order/arrangement/position matters — selections for posts, arranging objects, forming numbers, codes

**Use Combinations (ⁿCᵣ):** When only selection matters — committees, teams, choosing items, subsets

**Common Pitfall:** Confusing whether order matters. Read carefully: "arrange" → permutation; "select/choose" → combination

**Handling Restrictions:**

Identify restricted elements first

Fix restricted positions before permuting remaining

Use complementary counting if easier (total - unwanted cases)

**Factorial Simplification:**

Always express using factorial formula

Cancel common factors before computing

Never calculate large factorials completely

**Multi-stage Problems:**

Divide problem into independent stages

Use multiplication principle for combining stages

Ensure each stage is counted correctly

This comprehensive chapter note covers all essential concepts, theorems, properties, and problem-solving techniques required for complete board exam preparation in Permutations and Combinations.