Session 01

Counting

4 hours · Week 1

Course Reader

This session draws from the Probability for Computer Scientists course reader by Chris Piech (Stanford CS109), specifically the Counting and Combinatorics chapters.

Learning Objectives

Apply the Sum Rule and Product Rule of counting
Use the Inclusion-Exclusion Principle when sets overlap
Count permutations of distinct and indistinct objects
Count combinations (unordered selections) using the binomial coefficient
Compute probabilities using counting with equally likely outcomes
Recognize which counting technique applies to a given problem

What is Counting?

An experiment in probability produces an outcome. Counting answers: How many possible outcomes can occur?

Examples

Experiment	Count	Outcomes
Roll one die	6	{1, 2, 3, 4, 5, 6}
Roll die, even only	3	{2, 4, 6}
Roll two dice	36	{(1,1), (1,2), ..., (6,6)}

Sum Rule of Counting

Sum Rule

If the outcome of an experiment can be either from Set A (where |A| = m) or Set B (where |B| = n), and A ∩ B = ∅, then the number of outcomes is:

Sum Rule (Mutually Exclusive)

|A| + |B| = m + n

The Sum Rule applies when choosing between mutually exclusive alternatives—one experiment with branching outcomes.

Product Rule of Counting

Product Rule

If an experiment has two parts, where the first part has outcomes from Set A (|A| = m) and the second part has outcomes from Set B (|B| = n), then the number of outcomes is:

Product Rule (Sequential Steps)

|A| × |B| = mn

The Product Rule applies when performing sequential steps—a multi-step experiment.

Practice: Sum or Product?

Think, Pair, Share

For each problem: Which rule applies? How many outcomes?

1. Video Streaming Servers

Your application has servers in 2 locations: San Jose (100 servers) and Boston (50 servers). A request is routed to one server. How many possible servers?

Solution

Sum Rule: The request goes to SJ or Boston (mutually exclusive).
100 + 50 = 150 servers

2. Rolling Two Dice

How many possible outcomes from rolling two 6-sided dice?

Solution

Product Rule: Roll die 1 and roll die 2 (sequential steps).
6 × 6 = 36 outcomes

3. String Orderings

How many different orderings of letters are possible for "BOBA"?

Solution

This requires more than Sum/Product rules—we'll return to this with permutations!

Inclusion-Exclusion Principle

What if the sets overlap? Simple addition double-counts the intersection.

Inclusion-Exclusion (Two Sets)

|A ∪ B| = |A| + |B| − |A ∩ B|

Key Insight

The Sum Rule is a special case where |A ∩ B| = 0.

Example: Transmitting Bytes

An 8-bit string is accepted if it starts with "01" or ends with "10".

A = strings starting with "01": 2⁶ = 64
B = strings ending with "10": 2⁶ = 64
A ∩ B = strings with both: 2⁴ = 16

Total = 64 + 64 − 16 = 112 strings

General Principle of Counting

The Product Rule extends to any number of steps:

General Product Rule

n₁ × n₂ × … × n_r = Π n_i

Example: License Plates

Pre-1982 California: 3 letters + 3 digits
26 × 26 × 26 × 10 × 10 × 10 = 17,576,000 plates

Present day: 1 digit + 3 letters + 3 digits
10 × 26 × 26 × 26 × 10 × 10 × 10 = 175,760,000 plates

How Many Unique Images?

Each pixel can be one of 17 million distinct colors. An image with n pixels has (17,000,000)ⁿ possible images.

Image	Pixels	Unique images
Tiny (4×3)	12	≈ 10⁸⁶
Thumbnail (20×15)	300	≈ 10^2,167
12 MP camera	12,000,000	≈ 10^86,696,638

For comparison, there are roughly 10⁸⁰ atoms in the observable universe. Even a tiny 12-pixel image already exceeds that.

Permutations

Permutation

A permutation is an ordered arrangement of objects.

The number of permutations of n distinct objects is:

Permutations of Distinct Objects

n! = n × (n−1) × (n−2) × … × 2 × 1

Example: Orderings of "BAYES"

How many letter orderings are possible? Apply the Product Rule step by step:

Step 1: Choose first letter — 5 options
Step 2: Choose second letter — 4 options
Step 3: Choose third letter — 3 options
Step 4: Choose fourth letter — 2 options
Step 5: Choose fifth letter — 1 option

5 × 4 × 3 × 2 × 1 = 5! = 120 orderings

Example: Phone Passcodes

A 6-digit passcode uses each of 6 distinct numbers exactly once. How many possible passcodes?

6! = 6 × 5 × 4 × 3 × 2 × 1 = 720 passcodes

What if you had no smudges, but knew it was 6 digits long (digits can repeat)?
10⁶ = 1,000,000 passcodes

Permutations with Repetition (Semi-distinct Objects)

If some objects are indistinguishable, swapping them doesn't create a new arrangement. We divide out the redundant orderings:

n! / (n₁! × n₂! × … × n_k!)

where n_i is the count of each repeated element.

Example: BOBA

How many orderings of "BOBA"? 4 letters, but B appears twice.

If we treat the two B's as distinct (B₁ and B₂), we get 4! = 24 arrangements. But for every unique ordering, there are 2! = 2 versions that look identical (swapping B₁ and B₂).

4! / 2! = 24 / 2 = 12 orderings

Example: MISSISSIPPI

11 letters: M(1), I(4), S(4), P(2)

11! / (1! × 4! × 4! × 2!) = 34,650 orderings

Python: Permutations

import itertools
import math

# All orderings of BAYES (distinct letters)
letters = ['B', 'A', 'Y', 'E', 'S']
perms = list(itertools.permutations(letters))
print(len(perms))  # 120

# Unique orderings of BOBA (repeated letters)
letters = ['B', 'O', 'B', 'A']
unique_perms = set(itertools.permutations(letters))
print(len(unique_perms))  # 12

# Or compute directly:
print(math.factorial(4) // math.factorial(2))  # 12

Combinations

Combination

A combination is an unordered selection of k objects from a set of n distinct objects.

The key question: Does the order of selection matter? If yes → permutation. If no → combination.

Deriving the Formula: Combinations with Cake

There are n = 20 people. How many ways can we choose k = 5 people to get cake?

Consider a generative process:

Line up all n people — n! ways
Take the first k as the cake group — 1 way
Allow the cake group to mingle — k! orderings of the chosen group all lead to the same selection, so divide by k!
Allow the non-cake group to mingle — (n−k)! orderings of the unchosen group all lead to the same selection, so divide by (n−k)!

Combinations (Binomial Coefficient)

C(n, k) = (ⁿ_k) = n! / (k! × (n−k)!)

Symmetry

C(n, k) = C(n, n−k). Choosing who gets cake is the same as choosing who doesn't.

Example: Probability Textbooks

How many ways to choose 3 books from 6 distinct books?

C(6, 3) = 6! / (3! × 3!) = 720 / 36 = 20 ways

Permutations vs Combinations

	Order matters	Order doesn't matter
All n objects	n! (permutation)	1 (just one set)
Choose k of n	n! / (n−k)!	n! / (k!(n−k)!) = C(n,k)

Python: Combinations

import itertools
import math

# All ways to choose 3 books from 6
combos = list(itertools.combinations([1,2,3,4,5,6], 3))
print(len(combos))  # 20

# Or compute directly:
print(math.comb(6, 3))  # 20

# How many unique 5-card hands from a 52-card deck?
print(math.comb(52, 5))  # 2,598,960

Probabilities with Equally Likely Outcomes

When all outcomes in the sample space are equally likely:

Equally Likely Outcomes

P(E) = |E| / |S|

where |E| = number of outcomes in the event, |S| = total outcomes in the sample space.

Key Insight

For this formula to work, outcomes must be equally likely. The trick: make indistinct items distinct to get an equally likely sample space.

Example: Straight Poker Hand

A "straight" is 5 consecutive rank cards of any suit. What is P(straight)?

Solution

|S| = C(52, 5) = 2,598,960 possible 5-card hands
|E| = 10 starting ranks (A-5 through 10-A) × 4⁵ suit choices = 10 × 1,024 = 10,240
P(straight) = 10,240 / 2,598,960 ≈ 0.00394

Example: Bunnies and Foxes

4 bunnies and 3 foxes in a toy box. 3 are drawn. What is P(1 bunny and 2 foxes)?

Which sample space?

We need equally likely outcomes. Treat each animal as distinct (even if bunnies look alike).

	Distinct	Indistinct
Unordered	{F₁, B₂, B₃} ✔	{2 foxes, 1 bunny}
Ordered	[F₁, B₂, B₃] ✔	[fox, bunny, fox]

The distinct columns give equally likely outcomes. Either works!

Solution (unordered, distinct)

|S| = C(7, 3) = 35
|E| = C(4, 1) × C(3, 2) = 4 × 3 = 12
P(1 bunny, 2 foxes) = 12/35 ≈ 0.343

Example: Chip Defect Detection

n chips manufactured, 1 defective. k chips randomly selected for testing. What is P(defective chip is in the selected batch)?

Solution

|S| = C(n, k)
|E| = C(1, 1) × C(n−1, k−1) — must include the 1 defective, choose remaining k−1 from the n−1 good chips
P(defective selected) = C(n−1, k−1) / C(n, k) = k / n

A beautifully intuitive result: the chance is simply the fraction of chips you test.

The Complement Trick

Sometimes it's easier to count what you don't want: P(E) = 1 − P(E^C).

Example: P(at least one match) = 1 − P(no matches at all). This avoids complicated case-by-case counting.

Example: Card Shuffles & Uniqueness

A shuffled 52-card deck has one of 52! ≈ 8 × 10⁶⁷ possible orderings.

What is the probability that a single shuffle produces the same ordering as yours?

Solution

|S| = 52!
P(same) = 1 / 52! < 10⁻⁶⁷
P(different) = (52! − 1) / 52! = 0.9999...9 (about 68 nines)

Every time you properly shuffle a deck, you almost certainly produce an ordering that has never existed before in human history.

Summary: Choosing the Right Technique

Situation	Technique	Formula
Choose A or B (no overlap)	Sum Rule	\|A\| + \|B\|
Choose A or B (overlap)	Inclusion-Exclusion	\|A\| + \|B\| − \|A ∩ B\|
Do step 1 and step 2	Product Rule	n₁ × n₂
Order n distinct objects	Permutation	n!
Order with repeats	Permutation (repeated)	n! / (n₁! × ...)
Choose k of n (order doesn't matter)	Combination	C(n, k) = n! / (k!(n−k)!)
Probability (equally likely)	Count & divide	P(E) = \|E\| / \|S\|

Readings

Primary Reading
CS109: Counting – Sum Rule, Product Rule, Inclusion-Exclusion
Primary Reading
CS109: Combinatorics – Permutations and the six counting patterns
Full Course Reader
Probability for Computer Scientists – Stanford CS109 by Chris Piech

Practice Problems

Exercises: Counting, Permutations & Combinations →

Problem Set 01 →

How many 8-character passwords use A-Z and 0-9? How many require at least one digit? (Product Rule, Complement)
A committee of 5 from 12 people designates a chair and vice-chair. How many ways? (Combinations + Permutations)
How many orderings of "MISSISSIPPI"? (Permutations with repetition)
If 367 people are in a room, prove that at least two share a birthday. (Pigeonhole)
How many bit strings of length 10 start with "11" or end with "00"? (Inclusion-Exclusion)
A class has 15 students. How many ways to form a study group of 4? (Combinations)
A bag has 5 red and 4 blue marbles. You draw 3 at random. What is P(exactly 2 red)? (Combinations + Equally Likely Outcomes)
In a standard 52-card deck, what is P(all 5 cards are hearts)? (Combinations + Equally Likely Outcomes)

← Back to Sessions · Next: Probability →