Permutations & Combinations

🎯 1. Learning Objectives

After completing this topic, you should be able to:

Apply the addition and multiplication principles of counting.
Evaluate factorials and simplify factorial expressions.
Recognize whether order matters in a counting problem.
Calculate permutations and combinations.
Handle repeated objects, repetition, restrictions and circular arrangements.
Estimate program search spaces, subsets and possible test inputs.

🧠 2. Fundamental Counting Principles

Multiplication Principle

If one task has m choices and the next independent task has n choices, the combined task has m × n possibilities.

3 shirts × 2 trousers = 6 outfits

Addition Principle

If exactly one of two non-overlapping alternatives is chosen, add their counts.

4 bus routes + 3 train routes = 7 choices

First question: Are the choices performed together or are they alternatives? This decides whether to multiply or add.

❗ 3. Factorial

Factorial counts the arrangements of all n distinct objects.

5 choices

4 choices

3 choices

2 × 1

n! = n(n−1)(n−2)...2×1 and 0! = 1

Example: 5! = 5×4×3×2×1 = 120 arrangements.

🏁 4. Permutations: Order Matters

A permutation selects and arranges r objects from n distinct objects.

ⁿPᵣ = n! / (n−r)!

Example

A gold, silver and bronze order is chosen from 8 runners.

⁸P₃ = 8×7×6 = 336

Why Order Matters

A–B–C and B–A–C contain the same people but assign different ranks, so they are different outcomes.

👥 5. Combinations: Order Does Not Matter

A combination selects r objects from n distinct objects without arranging them.

ⁿCᵣ = n! / [r!(n−r)!]

Example

Select a 3-member team from 8 students.

⁸C₃ = 56 teams

Useful Identities

ⁿC₀ = ⁿCₙ = 1 and ⁿCᵣ = ⁿCₙ₋ᵣ.

⁸C₃ = ⁸C₅

🔍 6. Permutation or Combination?

Use Permutation

Rank or position is assigned.
Objects are arranged in a line.
Changing order creates a new result.
Examples: passwords, schedules, race results.

Use Combination

Only a group is selected.
Positions are not assigned.
Changing order does not create a new result.
Examples: teams, committees, subsets.

Question	Order?	Method
Choose a captain and vice-captain	Yes	Permutation
Choose two representatives	No	Combination
Create a four-character code	Yes	Multiplication/permutation
Select test cases from a test pool	No	Combination

🔁 7. Arrangements with Repeated Objects

When some objects are identical, divide by the factorial of each repeated count.

Arrangements = n! / (p!q!r!...)

BANANA: 6 letters with A repeated 3 times and N repeated 2 times. Count = 6!/(3!2!) = 60.

⭕ 8. Circular Permutations

Rotations of the same circular arrangement are treated as identical.

n distinct objects around a circle = (n−1)!

Five people around a round table can be seated in (5−1)! = 24 ways.

🔐 9. Repetition and Restrictions

Repetition Allowed

With n symbols and r positions, each position has n choices.

nʳ strings

Four decimal digits: 10⁴ = 10,000 codes.

Objects Together

Treat required adjacent objects as one block, then arrange the block internally.

2 particular people together among 6: 5! × 2!

Complement method: “At least one” is often easier as total outcomes minus outcomes with none.

INTERACTIVE EXPLORER

🧪 10. Counting Explorer

Choose a counting model, enter n and r where required, then click Calculate Count. Inputs alone never reveal the result.

Counting model

Number of objects n

Selected positions r

Select a model or example, then click Calculate Count.

💻 11. Applications in Programming

Brute-Force Search

Trying every ordering of n items may require n! cases. Factorial growth explains why brute force quickly becomes impractical.

Subsets and Bitmasks

A set with n elements has 2ⁿ subsets. Bitmasks encode whether each element is selected.

Password Search Space

A password of length r from n allowed symbols has nʳ possibilities when repetition is allowed.

Test-Case Selection

Selecting r cases from n without caring about execution order uses nCr.

🧾 12. Solved Problems

Problem 1: Ranked Selection

Problem: Choose president, secretary and treasurer from 7 students.

Solution: Roles differ, so order matters. ⁷P₃ = 7×6×5 = 210.

Problem 2: Team Selection

Problem: Select 4 programmers from 10.

Solution: Order does not matter. ¹⁰C₄ = 210.

Problem 3: Repeated Letters

Problem: Arrange the letters of LEVEL.

Solution: L and E each repeat twice. Count = 5!/(2!2!) = 30.

Problem 4: Search Space

Problem: Form a three-character string from 26 letters with repetition.

Solution: Each position has 26 choices: 26³ = 17,576.

✍️ 13. Practice Problems

Solve each problem first, then use Show Solution to verify your method.

1. In how many ways can 6 distinct books be arranged on a shelf?

2. How many 3-member teams can be selected from 9 students?

3. How many 4-character strings can be formed from 6 different symbols without repetition?

4. How many distinct arrangements does the word BOOK have?

5. How many non-empty subsets does a 6-element set have?

📝 14. Quick Revision

Use multiplication for successive independent choices and addition for alternatives.
n! arranges all n distinct objects; 0! = 1.
Permutation: order matters; ⁿPᵣ = n!/(n−r)!.
Combination: order does not matter; ⁿCᵣ = n!/[r!(n−r)!].
Divide by repeated factorials when identical objects occur.
Distinct circular arrangements = (n−1)!.
With repetition, r positions from n symbols produce nʳ strings.
A set of n elements has 2ⁿ subsets and 2ⁿ−1 non-empty subsets.

INTERACTIVE PRACTICE