Chapter 14: Permutation and Combination

Overview

Permutation and combination are fundamental counting techniques that provide systematic ways to count objects and arrangements. This chapter explores the fundamental counting principle, permutations (arrangements), and combinations (selections) along with their applications in probability and real-world problems. Mastery of these concepts is essential for solving problems in probability, statistics, computer science, and decision-making processes.

Learning Objectives

After completing this chapter, you will be able to:

• Understand and apply the fundamental counting principle
• Calculate permutations and their various types
• Compute combinations and understand their relationship to permutations
• Apply these concepts to solve probability problems
• Use counting techniques in real-world scenarios

Key Concepts

14.1 Fundamental Counting Principle

Statement of Counting Principle

The fundamental counting principle states that if there are m ways to do one thing and n ways to do another, then there are m × n ways to do both.

General Form: For a sequence of k independent choices with $n_1$, $n_2$, ..., nₖ alternatives respectively:

$$\text{Total ways} = n_1 \times n_2 \times \cdots \times n_k$$

Applications

Used when:

• Making multiple independent decisions
• Finding total outcomes for compound events
• Determining total possibilities in multi-step processes

14.2 Permutation

Definition of Permutation

A permutation is an arrangement of objects in a specific order. The order matters in permutations.

Number of Permutations: For arranging n distinct objects:

$$P(n) = n! = n \times (n-1) \times (n-2) \times \cdots \times 1$$

Types of Permutations

1. Permutation of n distinct objects taken r at a time:

$$P(n, r) = \frac{n!}{(n-r)!} = n \times (n-1) \times \cdots \times (n-r+1)$$

2. Permutation of n objects with repetitions:

$$\frac{n!}{n_1! \times n_2! \times \cdots \times n_k!}$$

Where $n_1$, $n_2$, ..., nₖ are the frequencies of identical objects.

3. Circular permutations:

$$\text{Linear} = (n-1)! \quad \text{and} \quad \text{Clockwise/Counterclockwise} = \frac{(n-1)!}{2}$$

Permutation with Restrictions

• Fixed positions: Objects that must be in specific positions
• Adjacency rules: Objects that must be together or separated
• Advanced constraints: Multiple simultaneous restrictions

14.3 Combination

Definition of Combination

A combination is a selection of objects where order does not matter.

Formula for Combinations:

$$C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$$

Relationship to Permutation

$$C(n, r) = \frac{P(n, r)}{r!} = \frac{P(n, r)}{r \times (r-1) \times \cdots \times 1}$$

This relationship shows that combinations are permutations divided by the number of ways to arrange the selected items.

Special Cases

• C(n, 0) = 1: There's one way to choose nothing
• C(n, n) = 1: There's one way to choose everything
• C(n, 1) = n: There are n ways to choose one item from n

Important Formulas and Methods

Key Counting Formulas

Problem-Solving Strategies

Permutation Problems:

1. Determine if order matters
2. Identify any restrictions or conditions
3. Choose appropriate permutation formula
4. Calculate step by step
5. Verify results make sense

Combination Problems:

1. Determine if order matters
2. Identify what is being selected
3. Choose appropriate combination formula
4. Calculate carefully
5. Interpret the result

Mixed Problems:

1. Break into sequential steps
2. Apply counting principle between steps
3. Use appropriate techniques within each step

Solved Examples

Example 1: Fundamental Counting Principle

A restaurant offers 3 appetizers, 4 main courses, and 2 desserts. How many different meals can be formed?

Solution:

Using fundamental counting principle:

• Appetizers: 3 choices
• Main courses: 4 choices
• Desserts: 2 choices
• Total meals = 3 × 4 × 2 = 24 different meals

Example 2: Permutation Without Repetition

How many different ways can 5 students be arranged in a line for a photograph?

Solution:

This is a permutation of 5 distinct objects taken 5 at a time: P(5, 5) = 5! = 5 × 4 × 3 × 2 × 1 = 120 arrangements

Example 3: Permutation With Restrictions

How many ways can the letters in "BANANA" be arranged?

Solution:

This is a permutation with repetitions:

• Total letters: 6
• Identical A's: 3
• Identical N's: 2

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

Example 4: Permutation of n Objects Taken r at a Time

How many 3-digit numbers can be formed from the digits 1, 2, 3, 4, 5 if: a) No repetition allowed b) Repetition allowed

Solution:

a) No repetition: P(5, 3) = 5! / (5-3)! = 120 / 2 = 60 numbers

b) Repetition allowed: Using counting principle:

• Hundreds digit: 5 choices
• Tens digit: 5 choices
• Units digit: 5 choices
• Total: 5 × 5 × 5 = 125 numbers

Example 5: Circular Permutation

In how many ways can 6 people sit around a circular table?

Solution:

For circular arrangements: Number of ways = (6 - 1)! = 5! = 120 arrangements

Example 6: Combination Basics

A committee of 3 people is to be selected from 7 candidates. How many different committees can be formed?

Solution:

This is a combination problem since order doesn't matter in committee selection: C(7, 3) = 7! / [3!(7-3)!] = 7! / (3! × 4!) = (7 × 6 × 5) / (3 × 2 × 1) = 35 committees

Example 7: Combination with Restrictions

From 5 men and 3 women, how many committees of 4 people can be formed if: a) There are no restrictions b) The committee must have exactly 2 men and 2 women c) The committee must have at least 2 men

Solution:

a) No restrictions: C(8, 4) = 70 committees

b) Exactly 2 men and 2 women: C(5, 2) × C(3, 2) = 10 × 3 = 30 committees

c) At least 2 men:

• 2 men + 2 women: C(5, 2) × C(3, 2) = 10 × 3 = 30
• 3 men + 1 woman: C(5, 3) × C(3, 1) = 10 × 3 = 30
• 4 men + 0 women: C(5, 4) × C(3, 0) = 5 × 1 = 5
• Total = 30 + 30 + 5 = 65 committees

Example 8: Probability Using Combinations

A bag contains 3 red marbles and 2 blue marbles. If 2 marbles are drawn at random, what is the probability of getting: a) Both red marbles b) One red and one blue marble

Solution:

Total ways to draw 2 marbles from 5: C(5, 2) = 10

a) Both red: C(3, 2) = 3 ways Probability = 3/10 = 0.3

b) One red and one blue: C(3, 1) × C(2, 1) = 3 × 2 = 6 ways Probability = 6/10 = 0.6

Mathematical Derivations

Derivation of Permutation Formula

For arranging n objects taken r at a time:

• First position: n choices
• Second position: n-1 choices
• ...
• r-th position: n-r+1 choices

Total arrangements = n × (n-1) × ⋯ × (n-r+1) = n!/(n-r)!

Derivation of Combination Formula

The number of combinations C(n, r) is the number of permutations divided by the number of ways to arrange the r selected items: C(n, r) = P(n, r) / r! = [n!/(n-r)!] / r! = n!/[r!(n-r)!]

Derivation of Permutation with Repetition

For n objects with $n_1$ identical of type 1, $n_2$ identical of type 2, ..., nₖ identical of type k (where $n_1$ + $n_2$ + ⋯ + nₖ = n):

Total permutations = Total permutations if all objects were distinct ÷ Number of ways to arrange identical objects within each type = n! / ($n_1$! × $n_2$! × ⋯ × nₖ!)

Real-World Applications

1. Computer Science and Programming

Algorithm Design:

• Counting possible paths in algorithms
• Calculating combinatorial complexity
• Optimizing search spaces

Example: Counting the number of possible binary strings of length n with exactly k ones.

2. Business and Economics

Decision Making:

• Product portfolio selection
• Investment combinations
• Marketing strategy optimization

Example: A company has 10 products and wants to create product bundles of 3 items. How many different bundles can be created?

3. Genetics and Biology

DNA Sequencing:

• Counting possible genetic combinations
• Analyzing genetic diversity
• Studying inheritance patterns

Example: How many different ways can 4 genes be arranged in a sequence?

4. Games and Entertainment

Game Theory:

• Calculating possible game outcomes
• Designing game mechanics
• Probability calculations

Example: How many different poker hands are possible?

Complex Problem-Solving Techniques

Problem: How many 4-letter words can be formed from the word "MATHEMATICS" if:

a) No restrictions b) Must start with a vowel c) Must have exactly one 'T'

Solution:

Total letters: 11 (M:2, A:2, T:2, H:1, E:1, I:1, C:1, S:1)

a) No restrictions: 11! / (2! × 2! × 2!) = 11! / 8 = 4,989,600 words

b) Must start with a vowel:

• Vowels: A, A, E, I (4 choices for first position)
• Remaining letters: 10 with repetitions
• Total: 4 × 10! / (2! × 2! × 2!) = 4 × 1,133,400 = 4,533,600 words

c) Must have exactly one 'T':

• Select position for T: 4 choices
• Select which T to use: 2 choices (but they're identical, so this doesn't matter)
• Remaining 3 positions: Choose 9 letters (without one T)
• Total: 4 × [9! / (2! × 2! × 1!)] = 4 × 90,720 = 362,880 words

Problem: A password must be 6 characters long and contain:

• At least 1 uppercase letter (A-Z)
• At least 1 lowercase letter (a-z)
• At least 1 digit (0-9)

How many possible passwords satisfy these conditions?

Solution:

Total possibilities without restrictions: 26 + 26 + 10 = 62 characters Total without restrictions: 62⁶ = 56,800,235,584

Using complementary counting:

• No uppercase: 36⁶ = 2,176,782,336
• No lowercase: 36⁶ = 2,176,782,336
• No digit: 52⁶ = 19,770,609,664

But these overlap:

• No uppercase AND no lowercase: 10⁶ = 1,000,000
• No uppercase AND no digit: 26⁶ = 308,915,776
• No lowercase AND no digit: 26⁶ = 308,915,776
• No uppercase, no lowercase, no digit: 0 (impossible)

Using inclusion-exclusion: Invalid = (no uppercase) + (no lowercase) + (no digit) - (no uppercase AND no lowercase) - (no uppercase AND no digit) - (no lowercase AND no digit) + (no uppercase AND no lowercase AND no digit) = 2,176,782,336 + 2,176,782,336 + 19,770,609,664 - 1,000,000 - 308,915,776 - 308,915,776 + 0 = 24,506,341,784

Valid = Total - Invalid = 56,800,235,584 - 24,506,341,784 = 32,293,893,800 passwords

Problem: How many ways can the numbers 1, 2, 3, 4, 5, 6 be arranged such that:

• The odd numbers are in increasing order
• The even numbers are in decreasing order

Solution:

Total numbers: 6 (3 odd: 1,3,5; 3 even: 2,4,6)

For any arrangement, the relative order of odd numbers must be 1,3,5 and even numbers must be 6,4,2.

Choose 3 positions out of 6 for the odd numbers (the remaining 3 will be for even numbers): C(6, 3) = 20 ways

The odd numbers fill their positions in increasing order, and even numbers fill theirs in decreasing order.

Total arrangements: 20

Summary Points

• Fundamental Counting Principle: Multiply the number of choices for each independent decision
• Permutations: Arrangements where order matters (nPr = n!/(n-r)!)
• Combinations: Selections where order doesn't matter (nCr = n!/[r!(n-r)!])
• Circular Permutations: (n-1)! for arrangements around a circle
• Repeated Objects: Divide by factorials of identical object counts
• Probability Applications: Use combinations to count favorable and total outcomes

Common Mistakes to Avoid

1. Order confusion - Determine whether order matters before choosing permutations vs combinations
2. Repetition errors - Check if objects are distinct or identical when applying formulas
3. Restriction oversight - Account for all constraints in complex problems
4. Calculation errors - Be careful with factorials and division
5. Interpretation errors - Understand whether results represent arrangements or selections

SPM Exam Tips

Exam Strategies

1. Identify the type - Determine if order matters for each problem
2. Check for repetitions - Watch for identical objects
3. Apply restrictions step by step - Handle constraints systematically
4. Use complementary counting - Sometimes it's easier to calculate unwanted outcomes
5. Practice mental math - Be comfortable with factorial calculations

Key Exam Topics

• Fundamental counting principle applications (15% of questions)
• Simple permutations and combinations (30% of questions)
• Permutations with repetitions (20% of questions)
• Combinations with restrictions (25% of questions)
• Probability applications (10% of questions)

Time Management Tips

• Counting principle problems: 3-4 minutes
• Simple permutation problems: 4-5 minutes
• Simple combination problems: 4-5 minutes
• Complex restricted problems: 7-9 minutes
• Probability applications: 6-8 minutes

Practice Problems

Level 1: Fundamental Counting Principle

1. A restaurant has 4 appetizers, 6 main courses, and 3 desserts. How many different meals can be created?

2. A license plate consists of 2 letters followed by 3 digits. How many possible license plates can be formed?

Level 2: Permutations

3. How many ways can 7 books be arranged on a shelf?

4. How many 4-digit numbers can be formed from {1,2,3,4,5} if: a) No repetition b) Repetition allowed

5. In how many ways can the letters in "MISSISSIPPI" be arranged?

Level 3: Combinations

6. A committee of 5 is to be selected from 12 people. How many different committees can be formed?

7. From 6 boys and 4 girls, how many teams of 3 can be formed if: a) No restrictions b) Exactly 2 boys c) At least 2 girls

Level 4: Complex Problems

8. How many ways can 10 people sit at a round table if 3 specific people must sit together?

9. How many 5-letter words can be formed from "COMPUTER" if: a) Must contain exactly 2 vowels b) Must start and end with consonants

Level 5: Applications

10. Probability: A box has 5 red and 3 blue balls. If 3 balls are drawn, find the probability of: a) All red b) 2 red and 1 blue c) At least 1 red

11. Business: A company has 8 products. How many ways can they choose: a) 3 products for a promotion b) 4 products for a store display c) 5 products for a catalog

12. Sports: A tournament has 16 teams. How many different ways can: a) 4 teams be selected for semifinals b) 1st, 2nd, and 3rd places be awarded

Did You Know? 📚

The study of combinatorics dates back to ancient times. Indian mathematician Pingala (3rd century BCE) studied permutations and combinations in the context of poetic meters. The binomial coefficients (combinations) were discovered independently by mathematicians in many different cultures, including Chinese mathematician Yang Hui in the 13th century. Today, combinatorics is fundamental in computer science, cryptography, and statistical physics, making it one of the most important branches of discrete mathematics.

Quick Reference Guide

---

Permutation and combination provide the foundation for counting and probability theory. Master these concepts as they are essential for solving complex problems in mathematics, science, and real-world decision-making scenarios.