Combinatorics: Counting, Permutations & Combinations

Discrete Mathematics Fundamentals

Chapter 9 · Combinatorics: Counting, Permutations & Combinations

Chapter 1 named combinatorics as underlying complexity analysis, cryptographic keyspace sizing, and test-case counting. Chapter 6 forward-referenced the pigeonhole principle. This chapter delivers the actual toolkit — starting from one foundational rule everything else in combinatorics is built from.

The Multiplication Principle

If one choice can be made in m ways, and a second, independent choice can be made in n ways, the two together can be made in m × n ways.

This is exactly what nested loops compute

A loop of size m nested inside a loop of size n executes its inner body exactly m × n times — the multiplication principle, running as code. Choosing among 3 colors and 4 sizes independently gives 3 × 4 = 12 total product variants, the same underlying arithmetic either way.

Factorial

n! ("n factorial") is the number of ways to arrange n distinct items in a sequence, using every item exactly once: n! = n × (n-1) × ... × 2 × 1. By convention, 0! = 1 — there's exactly one way to arrange zero items: the empty arrangement, doing nothing at all.

Permutations — Order Matters

P(n, r) = n! / (n − r)! counts the number of ways to choose and arrange r items from a set of n distinct items, where order matters. Ranking the top 3 finishers out of 10 racers is a permutation — 1st, 2nd, and 3rd place are genuinely different outcomes even with the same three people involved.

Combinations — Order Doesn't Matter

C(n, r) = n! / (r! (n − r)!), often written "n choose r," counts the number of ways to choose r items from n where order is irrelevant. Choosing a 3-person committee from 10 people is a combination — there's no "1st, 2nd, 3rd" committee member, just membership.

The one question that tells you which formula to use

Does the arrangement or order of the selected items actually matter for this problem? If yes — permutation. If no — combination. Nearly every mistake in this topic comes from skipping this question and guessing instead.

How the Two Formulas Relate

C(n, r) = P(n, r) / r! — every combination of r items corresponds to exactly r! different permutations (every possible ordering of that same selected group). Combinations divide out exactly the "redundant" orderings that permutations count separately. The two aren't unrelated formulas — combinations are permutations with the ordering information deliberately discarded.

The Pigeonhole Principle — Formalized

Chapter 6 already used this reasoning without naming it: if n items are placed into m containers and n > m, at least one container must hold more than one item.

The generalized version, and where Chapter 6's own "10,000 possible PINs" came from

The stronger, generalized form: if n items go into m containers, at least one container holds at least ⌈n/m⌉ items (rounding up). Chapter 6's own PIN exercise — 15,000 users, only 10,000 possible 4-digit PINs — concluded at least one PIN had to be shared by at least ⌈15000/10000⌉ = 2 users, exactly this formula in action. And that "10,000 possible PINs" figure itself comes straight from this chapter's own multiplication principle: 10 choices for each of 4 digits, with repetition allowed, gives 10 × 10 × 10 × 10 = 10⁴ = 10,000.

Three Counting Scenarios, Side by Side

Scenario	Formula	Example
Order matters, no repetition	P(n,r) = n!/(n−r)!	Ranking 3 medal winners from 10 racers
Order doesn't matter, no repetition	C(n,r) = n!/(r!(n−r)!)	Choosing a 3-person committee from 10 people
Order matters, repetition allowed	n^r	A 4-digit PIN, digits can repeat

Hands-On Exercises

Exercise 1

In how many ways can gold, silver, and bronze medals be awarded among 8 racers? Use the appropriate formula and show your work.

📄 View solution

Exercise 2

How many different 3-person teams can be formed from a pool of 8 people? Compute this, and explain specifically why the answer is smaller than Exercise 1's own result, even though both start from the same 8 people and select 3.

📄 View solution

Exercise 3

A room contains 32 people. Using the generalized pigeonhole principle, prove that at least 5 of them must share the same day-of-the-week birthday (Monday, Tuesday, etc. — 7 possible days).

📄 View solution

Chapter 9 Quick Reference

Multiplication principle: independent choices of m and n ways combine to m × n total ways — exactly what nested loops compute
n! = ways to arrange n distinct items in order; 0! = 1 by convention
Permutation P(n,r) = n!/(n−r)! — order matters
Combination C(n,r) = n!/(r!(n−r)!) — order doesn't matter; C(n,r) = P(n,r)/r!
The one question that decides which formula: does order/arrangement actually matter here?
Pigeonhole principle: n items into m containers (n>m) guarantees a shared container; generalized form guarantees at least ⌈n/m⌉ in some container
Next chapter: Capstone — applying discrete math to real programming problems