The Sum Rule and Basic Permutations

Learn when to add vs multiply in counting, understand permutations and factorial notation.

22 min read
Beginner

Introduction

In Lesson 1, we learned to multiply choices for sequential stages. But what if we have multiple disjoint scenarios? That's where the Rule of Sum comes in. We'll also introduce permutations - ordered arrangements of objects.

Learning Objectives:

  • Master the Rule of Sum (Addition Principle)
  • Understand when to add vs multiply in counting problems
  • Define and calculate permutations
  • Compute factorials and apply them to arrangement problems

The Rule of Sum

If a task can be done in one of several mutually exclusive ways:

  • Way 1: n1n_1 possibilities
  • Way 2: n2n_2 possibilities
  • ...
  • Way kk: nkn_k possibilities

Then the total number of ways is:

n1+n2+⋯+nkn_1 + n_2 + \cdots + n_k

Key requirement: The ways must be disjoint (mutually exclusive) - no outcome can be counted in multiple ways.

Example 1: Travel Options

You can travel from City A to City B by:

  • Bus: 5 different bus routes
  • Train: 3 different train routes
  • Flight: 2 different flights

How many total ways to travel from A to B?

Solution: The methods are mutually exclusive (you choose one):

5+3+2=10 ways5 + 3 + 2 = 10 \text{ ways}

You add because you're choosing one option from disjoint sets.

Add vs Multiply:

  • Add when choosing one option from disjoint scenarios
  • Multiply when making sequential choices at independent stages

Combining Rules

Most problems require both rules. The key is identifying the structure:

Example 2: Menu Selection

A restaurant offers:

  • Appetizers: Soup (1 type) or Salad (3 types)
  • Entrees: Pasta (4 types) or Steak (2 types)

How many different two-course meals (appetizer + entree)?

Solution:

  1. Appetizer choices: 1+3=41 + 3 = 4 (Rule of Sum - disjoint)
  2. Entree choices: 4+2=64 + 2 = 6 (Rule of Sum - disjoint)
  3. Total meals: 4×6=244 \times 6 = 24 (Rule of Product - sequential)

You add within each course (disjoint options), then multiply across courses (sequential stages).

python
# Restaurant menu
appetizers = {'Soup': 1, 'Salad': 3}
entrees = {'Pasta': 4, 'Steak': 2}

# Total choices at each stage (using Rule of Sum)
total_appetizers = sum(appetizers.values())
total_entrees = sum(entrees.values())

# Total meals (using Rule of Product)
total_meals = total_appetizers * total_entrees

print(f"Appetizer choices: {total_appetizers}")
print(f"Entree choices: {total_entrees}")
print(f"Total meal combinations: {total_meals}")

# Enumerate a few
print(f"\nExample meals:")
print(f"  1. Soup + Pasta (type 1)")
print(f"  2. Soup + Pasta (type 2)")
print(f"  3. Salad (type 1) + Steak (type 1)")
print(f"  ... (21 more combinations)")

Permutations

A permutation is an ordered arrangement of objects. The number of ways to arrange nn distinct objects is:

n!=n×(n−1)×(n−2)×⋯×2×1n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1

This is read as "nn factorial."

Special case: 0!=10! = 1 (by convention, for mathematical consistency)

Example 3: Arranging Books

You have 5 distinct books. How many ways can you arrange them on a shelf?

Solution:

  • Position 1: 5 choices
  • Position 2: 4 remaining choices
  • Position 3: 3 remaining choices
  • Position 4: 2 remaining choices
  • Position 5: 1 remaining choice

By the Rule of Product:

5×4×3×2×1=5!=120 arrangements5 \times 4 \times 3 \times 2 \times 1 = 5! = 120 \text{ arrangements}

python
import math

# Calculate 5!
n = 5
factorial_n = math.factorial(n)

print(f"{n}! = {factorial_n}")

# Show the calculation step by step
result = 1
steps = []
for i in range(n, 0, -1):
    result *= i
    steps.append(f"{i}")

print(f"\nCalculation: {' × '.join(steps)} = {result}")

# Fun fact: Growth of factorials
print(f"\nFactorial growth:")
for k in range(1, 11):
    print(f"  {k}! = {math.factorial(k):,}")

Exponential Growth: Factorials grow extremely fast! 10!≈3.610! \approx 3.6 million, 20!≈2.420! \approx 2.4 quintillion. This is why brute-force enumeration becomes infeasible quickly.

Partial Permutations

What if you only arrange some of the objects?

Example 4: Race Podium

In a race with 10 runners, how many ways can the top 3 finishers be arranged?

Solution: We're arranging 3 out of 10 objects:

  • 1st place: 10 choices
  • 2nd place: 9 remaining choices
  • 3rd place: 8 remaining choices

10×9×8=72010 \times 9 \times 8 = 720

General formula: Permutations of kk objects chosen from nn:

P(n,k)=n!(n−k)!P(n, k) = \frac{n!}{(n-k)!}

For our example:

P(10,3)=10!(10−3)!=10!7!=10×9×8=720P(10, 3) = \frac{10!}{(10-3)!} = \frac{10!}{7!} = 10 \times 9 \times 8 = 720

python
import math

def permutations(n, k):
    """Calculate P(n, k) = n! / (n-k)!"""
    return math.factorial(n) // math.factorial(n - k)

# Race with 10 runners, top 3 positions
n_runners = 10
k_positions = 3

result = permutations(n_runners, k_positions)

print(f"P({n_runners}, {k_positions}) = {result}")
print(f"\nThere are {result:,} possible podium arrangements")

# Verify with direct calculation
direct = 10 * 9 * 8
print(f"\nDirect calculation: 10 × 9 × 8 = {direct}")
print(f"Match: {result == direct}")

Avoiding Double Counting

A common error: counting the same outcome multiple times.

Example 5: Committee Formation (Wrong Approach)

Select a president and vice president from 5 people. One approach:

Wrong: "Choose president (5 ways), then choose VP (5 ways) = 5×5=255 \times 5 = 25"

Problem: This counts scenarios where the same person is both president and VP!

Correct: "Choose president (5 ways), then choose VP from remaining 4 people = 5×4=205 \times 4 = 20"

P(5,2)=5!3!=5×4=20P(5, 2) = \frac{5!}{3!} = 5 \times 4 = 20

Key Insight: When objects are selected without replacement, choices at later stages have fewer options. Always ask: "Does this choice affect future choices?"

Key Takeaways

  1. Rule of Sum: Add when choosing from disjoint scenarios
  2. Rule of Product: Multiply for sequential choices
  3. Factorial: n!=n×(n−1)×⋯×1n! = n \times (n-1) \times \cdots \times 1
  4. Permutation: Ordered arrangement, n!n! ways for nn objects
  5. Partial permutation: P(n,k)=n!(n−k)!P(n,k) = \frac{n!}{(n-k)!} for arranging kk out of nn
  6. Avoid double counting: Account for constraints (e.g., no replacement)

Next Lesson: We'll explore combinations - what if order doesn't matter?

Concept
Formula
Example
Rule of Sum$n_1 + n_2 + \cdots + n_k$Travel: $5 + 3 + 2 = 10$ options
Factorial$n!$$5! = 120$
Permutation (all)$n!$Arrange 5 books: $5! = 120$
Permutation (k of n)$\frac{n!}{(n-k)!}$Top 3 from 10: $\frac{10!}{7!} = 720$
🎲

Combinatorics and Probability: From Counting to Inference

Master the mathematical foundations of counting, probability, and randomness. This comprehensive course bridges pure combinatorics with computational probability, covering everything from basic counting principles to advanced probabilistic methods, limit theorems, and real-world applications in algorithms, finance, and data science.