Metadata Card

• Prerequisites: Chapter 5 — Relations and Functions
• Estimated time: 45 minutes
• Core difficulty: Beginner
• Completion marker: Master the addition and multiplication principles, distinguish permutations from combinations, compute simple combinatorial numbers

Your Progress

You step out of the discrete mathematics tower, walk through a corridor, and enter the second tower — the Combinatorics Tower. This tower has no stone doors, but is filled with enormous abacuses. The Librarian stands before the first abacus, flicks a few beads: "Only a few beads, but how many states can they form?"

Your Task

Given 10 digits, how many different 4-digit passwords can you form? From an 8-person team, how many ways to select 3 people for a business trip? Permutations and combinations address the same fundamental problem: counting. Every possible state space size you encounter in software, every search space dimension, every test coverage calculation — they all depend on this.

Chapter Layers

• Required reading: Addition/multiplication principles, permutations, combinations
• Optional reading: Pigeonhole principle, binomial theorem

Breakthrough · Origin Story

You're designing a permission system: five roles, twenty resources, three operations (read, write, execute). You need to evaluate whether "the total number of possible permission combinations" is too large to exhaustively test. "Just a few hundred, right?" asks the boss. You don't know. What you're missing is the mathematical tools for counting.

Addition principle: If a task can be done in m mutually exclusive ways, where method 1 has n₁ ways, method 2 has n₂ ways, ..., the total number of ways is n₁ + n₂ + ... .

Multiplication principle: If a task has k steps, where step 1 has n₁ ways, step 2 has n₂ ways, ..., the total number of ways is n₁ × n₂ × ... .

Five roles, twenty resources, three operations:

• Each resource has three possible permission states for each role
• Total combinations = 3^(5 × 20) = 3^100

This number is too large to exhaustively test. Now you can answer the boss — and convince him to adopt policy-based testing instead of exhaustive enumeration.

Permutation: Selecting r elements from n distinct elements in order.

P(n, r) = n! / (n - r)!

For example, choosing a 4-digit password from 10 digits: P(10, 4) = 10 × 9 × 8 × 7 = 5040.

Combination: Selecting r elements from n distinct elements (order doesn't matter).

C(n, r) = n! / (r! × (n - r)!)

Selecting 3 people from 8 for a trip: C(8, 3) = 8! / (3! × 5!) = 56.

Key difference: permutations are ordered (password 1234 ≠ 4321), combinations are unordered (the team {Alice, Bob, Carol} and {Carol, Bob, Alice} are the same group).

Pascal's identity: C(n, k) = C(n-1, k-1) + C(n-1, k). The intuitive explanation: fix one element; combinations that include it number C(n-1, k-1), and those that exclude it number C(n-1, k). This is the mathematical basis for dynamic programming solutions to combinatorial numbers.

Pigeonhole principle: If n+1 pigeons are placed into n holes, at least one hole contains at least 2 pigeons. It sounds almost trivial, but it yields non-trivial conclusions:

• Among 366 people, at least two share a birthday (365 days max per year).
• Among 5 integers, at least 3 have the same parity (since there are only two parity classes, putting 5 into 2 holes).

This principle appears repeatedly in proofs about hash collisions: if the output space of a hash function is smaller than its input space, collisions are inevitable.

Common Pitfalls

• Confusing permutations and combinations. Asking "does order matter?" is the key to distinguishing them.
• Double-counting. When calculating "at least one condition is satisfied," it's easy to double-count cases that satisfy multiple conditions — this is where the inclusion-exclusion principle comes in.
• Thinking 0! = 0. Actually 0! = 1 — this is a convention that makes the combination formula work when n = r.

Challenge Questions

• A class of 30 students needs to elect a president, vice president, and academic chair, each a different person. How many ways?
• 10 distinct books are placed on 3 shelves (shelves are ordered), with at least one book per shelf. How many arrangements?
• Implement C(n, k) in Python using two methods: the factorial formula and dynamic programming (Pascal's triangle).

Traveler's Notes

Permutations are "ordered selections"; combinations are "unordered subsets." The addition and multiplication principles are the two basic tools of counting. The pigeonhole principle tells you "there must be" — together they form your first set of weapons for analyzing system state space.

→ Next stop: Sets and combinations both discuss "which elements," but the relationships between elements can be described by graphs — graph theory takes you from static sets to dynamic relationships.