1. Foundations and Combinatorics

This chapter sets up the vocabulary and tools that the rest of the guide relies on. It defines what data, populations and variables are, introduces the set language that probability is written in, and develops the counting techniques that turn "how likely is this?" into "how many ways can this happen?". Most probability calculations in Chapters 3 to 6 come down to one of these three ideas.

<a id="11-data-populations-and-variables"></a>

1.1 Data, Populations, and Variables

Before computing anything, we need to say exactly what we are studying, what we actually observe, and what kind of values the data can take.

Population vs. Sample

Why it matters. We almost never get to observe everything we care about. A pharmaceutical company wants to know how a drug affects all future patients, but it can only test a few thousand. A website wants to know what all its users prefer, but only some answer a survey. Statistics exists to bridge the gap between the part we see and the whole we care about.

Definitions.

• The population is the complete collection of units (people, machines, transactions, measurements) about which we want to draw conclusions.
• A sample is the subset of the population that we actually observe.
• An observational unit is a single member of the population (one patient, one transaction).
• A census is the special case where the sample is the entire population.
• The sampling frame is the list or mechanism from which the sample is actually drawn (for example, a customer database). When the frame does not match the population, conclusions can be biased (Section 7.4).

Populations can be finite (all 4,200 employees of a company) or conceptual (all future rolls of a die, all parts a machine will ever produce). Conceptual populations are infinite and can never be fully observed, which is why probability models are needed to describe them.

Analogy. Tasting soup. You do not drink the whole pot to judge the seasoning; one spoonful (the sample) tells you about the pot (the population), provided you stirred first. Stirring is randomization: it makes the spoonful representative. A spoonful taken from the surface of an unstirred pot is a biased sample.

        POPULATION (all units of interest)
   +---------------------------------------------+
   |  o   o    o      o   o     o    o    o      |
   |     o   +-----------------+    o     o   o  |
   |  o      |  SAMPLE         |  o    o         |
   |    o    |   *  *   *  *   |      o    o     |
   |  o    o |    *   *  *     |   o        o    |
   |         +-----------------+      o    o     |
   |   o   o     o    o   o     o   o     o      |
   +---------------------------------------------+
   We measure the *'s and want to learn about all the o's.

The simulation below builds a synthetic population of incomes and compares a summary of the full population to the same summary computed from a random sample of 500 units.

import numpy as np

rng = np.random.default_rng(42)          # fixed seed so results are reproducible

# A synthetic population of 100,000 annual incomes (right-skewed, like real incomes)
population = rng.lognormal(mean=10.5, sigma=0.6, size=100_000)

# Simple random sample: every unit has the same chance of being selected
sample = rng.choice(population, size=500, replace=False)

print(f"population mean: {population.mean():,.0f}")   # 43,442
print(f"sample mean:     {sample.mean():,.0f}")       # 42,906 -> close, not identical

Using only 0.5% of the population, the sample mean lands within about 1.2% of the population mean. That accuracy depends entirely on how the sample was drawn, not on how large the population is.

Key takeaways

• The population is what you want to know about; the sample is what you actually observe.
• A census observes the whole population, which is rare, expensive, and often impossible for conceptual populations.
• Random selection is what makes a sample representative; size alone does not fix a biased selection process.
• Always ask: "What population does this sample actually represent?" The answer is determined by the sampling frame.

🧪 Practice

1. A university emails a survey to all 30,000 students and 2,100 reply. Identify the population, the sampling frame, and the sample.
2. A factory inspects every 50th bottle that comes off a production line. What is the population? Is it finite or conceptual?
3. A news site runs a poll on its homepage asking "Should the city build a new stadium?" Explain why 50,000 responses may still tell you little about the city's residents.
4. Interview: You have the complete event logs for every user of your app last month. Is that a population or a sample? Hint: the answer depends on the question being asked. Consider questions about last month versus questions about next month's users.

Parameters vs. Statistics

Why it matters. Once we distinguish the population from the sample, we need to distinguish the numbers that describe each one. Confusing them leads to the most common error in reading statistics: treating a number computed from one sample as if it were the fixed truth.

Definitions.

• A parameter is a numerical characteristic of the population. It is a fixed constant, but it is usually unknown.
• A statistic is a numerical characteristic computed from the sample. It is known once the data are collected, but it changes from sample to sample.

A mnemonic: Population goes with Parameter, Sample goes with Statistic. By convention, parameters are written with Greek letters and statistics with Latin letters or "hats".

Quantity	Parameter (population)	Statistic (sample)
Mean	$\mu$	$\bar{x}$
Standard deviation	$\sigma$	$s$
Variance	$\sigma^2$	$s^2$
Proportion	$p$	$\hat{p}$
Correlation	$\rho$	$r$
Regression slope	$\beta_1$	$\hat{\beta}_1$ or $b_1$

Because a statistic depends on which units happened to be sampled, it is itself a random quantity. This property, called sampling variability, is the foundation of all inference: Chapter 7 studies the distribution of a statistic across repeated samples, and Chapter 8 uses statistics as estimators of parameters.

Analogy. The parameter is the true position of a target. Each statistic is one arrow shot at it. The target does not move, but each arrow lands somewhere different. Good estimation methods produce arrows that cluster tightly around the target.

import numpy as np

rng = np.random.default_rng(7)
population = rng.normal(loc=170, scale=10, size=50_000)   # heights in cm

print(f"mu = {population.mean():.2f}")                     # the parameter: fixed

for i in range(5):                                         # five independent samples of 40
    s = rng.choice(population, size=40, replace=False)
    print(f"sample {i + 1}: x_bar = {s.mean():.2f}")       # the statistic: varies

mu = 169.95
sample 1: x_bar = 170.21
sample 2: x_bar = 168.72
sample 3: x_bar = 169.85
sample 4: x_bar = 173.78
sample 5: x_bar = 173.11

The parameter $\mu$ printed once and never changes. The statistic $\bar{x}$ moves by several centimetres between samples, even though every sample came from the same population.

Key takeaways

• Parameters describe populations, are fixed, and are usually unknown.
• Statistics describe samples, are computed from data, and vary from sample to sample.
• Greek letters ($\mu, \sigma, p$) denote parameters; Latin letters and hats ($\bar{x}, s, \hat{p}$) denote statistics.
• A statistic used to estimate a parameter is called an estimator. Its sample-to-sample variability is what confidence intervals and tests quantify.

🧪 Practice

1. Classify each number as a parameter or a statistic: (a) "According to the national census, the median age is 41.2 years." (b) "In a poll of 1,000 likely voters, 52% support the measure." (c) "The average GPA of all students enrolled this semester is 3.12, computed from the registrar's database."
2. Write the correct symbol for each: the proportion of defective chips in one day's production of 10,000 chips (all inspected), and the proportion of defective chips among 200 chips tested.
3. Modify the code above to draw 1,000 samples of size 40 and plot a histogram of the $\bar{x}$ values. Where is it centred? Repeat with samples of size 160. What changes?
4. Interview: An A/B test reports a conversion rate of 4.1% for variant A and 3.8% for variant B. Are these parameters or statistics, and what does that imply for declaring A the winner? Hint: ask what would happen to both numbers if you re-ran the experiment with different users.

Qualitative and Quantitative Variables

Why it matters. The type of a variable determines which summaries, charts, and statistical methods are valid. Computing the "average blood type" makes no sense, and a bar chart of exact incomes is useless. Classifying variables correctly is the first step of any analysis.

Definitions. A variable is a characteristic that can take different values for different observational units.

• Qualitative (or categorical) variables place each unit into a category. Examples: blood type, country, product plan. A categorical variable with exactly two categories (yes/no, defective/not) is binary.
• Quantitative (or numerical) variables take numeric values for which arithmetic is meaningful. They split into two kinds:
  • Discrete: countable values, usually counts. Examples: number of children, number of orders, defects per wafer.
  • Continuous: any value in an interval, limited only by measurement precision. Examples: height, time, temperature, weight.

                       Variable
                  /                \
        Qualitative               Quantitative
        (categorical)              (numerical)
        /         \                /          \
   Nominal      Ordinal       Discrete     Continuous
  (no order)   (ordered)      (counts)   (measurements)
  blood type   rating 1-5   # of orders   height, time

The "numbers are not always numbers" trap. A variable recorded with digits is not necessarily quantitative. ZIP codes, phone numbers, jersey numbers, and product IDs are labels. The test is: does adding, subtracting, or averaging the values produce something meaningful? If not, the variable is categorical.

Variable	Type	Reason
Blood type (A, B, AB, O)	Qualitative, nominal	Categories with no order
T-shirt size (S, M, L, XL)	Qualitative, ordinal	Ordered categories
ZIP code	Qualitative, nominal	Digits are labels; averaging is meaningless
Number of siblings	Quantitative, discrete	Counts: 0, 1, 2, ...
Reaction time (ms)	Quantitative, continuous	Any value in an interval
Is a returning customer	Qualitative, binary	Two categories

Software does not know what your variables mean. pandas infers types from how values look, so ZIP codes are silently read as integers:

import io
import pandas as pd

csv = """customer_id,zip_code,plan,satisfaction,num_orders,monthly_spend
101,10001,basic,4,3,29.99
102,94105,premium,5,12,99.50
103,60614,basic,2,1,29.99
"""
df = pd.read_csv(io.StringIO(csv))
print(df.dtypes)
# customer_id        int64    <- an ID: actually categorical
# zip_code           int64    <- a label: actually categorical
# plan                 str    <- categorical, correctly detected ("object" in pandas < 3.0)
# satisfaction       int64    <- ordinal rating: categorical with order
# num_orders         int64    <- quantitative, discrete
# monthly_spend    float64    <- quantitative, continuous

print(df["zip_code"].mean())   # 54906.67 -> computes without error, but is meaningless

# Fix: declare the real types explicitly
df["zip_code"] = df["zip_code"].astype(str).astype("category")
df["satisfaction"] = pd.Categorical(df["satisfaction"], categories=[1, 2, 3, 4, 5], ordered=True)

Key takeaways

• Qualitative variables name categories; quantitative variables measure amounts with meaningful arithmetic.
• Quantitative variables are discrete (countable values) or continuous (any value in an interval).
• Digits do not make a variable quantitative. Check whether arithmetic on the values means anything.
• Software infers types from appearance, not meaning. Declare types explicitly before analysis.

🧪 Practice

1. Classify each variable as qualitative or quantitative, and quantitative ones as discrete or continuous: eye color, number of emails received per day, body temperature, credit card number, distance run in a marathon, number of goals scored.
2. Age can be recorded as "years since birth" (e.g., 34.7) or as "age bracket" (18-24, 25-34, ...). Classify each version and name one analysis that works for one but not the other.
3. A dataset stores "number of stars" for product reviews as integers 1 to 5. Argue both for treating it as discrete quantitative and as ordinal categorical.
4. Interview: You are building a linear regression model and one feature is region coded as 1 = North, 2 = South, 3 = East. What goes wrong if you feed it in as a number, and how do you fix it? Hint: what does a single slope coefficient on this column assume about the "distance" between North and East?

Levels of Measurement

Why it matters. The qualitative/quantitative split is useful but coarse. Two variables can both be numeric and still support different arithmetic: 40°C is not "twice as hot" as 20°C, but 40 kg is twice as heavy as 20 kg. Levels of measurement tell you which comparisons and operations are legitimate.

The four levels (Stevens' NOIR scale). Each level includes all the properties of the levels before it and adds one.

1. Nominal: categories with no inherent order. You can only check equality. Examples: nationality, blood type.
2. Ordinal: categories with a meaningful order, but the gaps between them are not necessarily equal. Examples: education level, survey ratings, race finishing position.
3. Interval: numeric values with equal, meaningful differences, but no true zero. Zero is an arbitrary point, so ratios are meaningless. Examples: temperature in °C or °F, calendar year, IQ scores.
4. Ratio: interval properties plus a true zero meaning "none of the quantity". Ratios are meaningful. Examples: height, mass, income, temperature in Kelvin, reaction time.

Level	Equal / not equal	Order	Differences	Ratios	Typical center	Example
Nominal	Yes	No	No	No	Mode	Blood type
Ordinal	Yes	Yes	No	No	Median, mode	Pain score 1-10
Interval	Yes	Yes	Yes	No	Mean, median, mode	Temperature °C
Ratio	Yes	Yes	Yes	Yes	All, incl. geometric mean	Weight in kg

   Nominal  ->  Ordinal  ->  Interval  ->  Ratio
   (=, !=)      (+ order)    (+ equal      (+ true zero,
                              differences)   meaningful ratios)
   more information and more permitted operations  ------------>

Why "no true zero" kills ratios. The zero of the Celsius scale is the freezing point of water, a convention. Shifting to a scale with a different zero changes the ratio, which proves the ratio was never a property of the physical quantity:

c_hot, c_cold = 20.0, 10.0
print(c_hot / c_cold)                       # 2.0 -> looks like "twice as hot"

k_hot, k_cold = c_hot + 273.15, c_cold + 273.15   # Kelvin has a true zero
print(round(k_hot / k_cold, 3))             # 1.035 -> only about 3.5% more thermal energy

f_hot, f_cold = c_hot * 9 / 5 + 32, c_cold * 9 / 5 + 32
print(f_hot / f_cold)                       # 1.36 -> a different "ratio" for the same temperatures
# Differences behave consistently: 10 C apart is always 18 F apart.

The ordinal gray zone. Likert scales ("strongly disagree" to "strongly agree", coded 1 to 5) are ordinal, but they are often averaged as if they were interval. This is common practice and frequently useful, but it assumes the step from 1 to 2 equals the step from 4 to 5. Medians and proportions are always safe; means need justification.

Key takeaways

• Nominal: categories only. Ordinal: ordered categories. Interval: equal differences, arbitrary zero. Ratio: true zero, so ratios mean something.
• The level determines which summaries are valid: mode for nominal, median for ordinal, mean for interval and ratio.
• Ratio statements ("twice as much") require a ratio scale.
• Averaging ordinal ratings is a modeling assumption, not a neutral operation.

🧪 Practice

1. Assign a level of measurement to: movie genre, Olympic medal (gold/silver/bronze), year of birth, annual salary, pH value, number of website visits.
2. Someone claims "it was 30°F yesterday and 60°F today, so today is twice as warm." Convert both to Celsius and to Kelvin and explain why the claim fails.
3. A customer-satisfaction survey uses the scale Poor = 1, Fair = 2, Good = 3, Excellent = 4. Product A averages 3.0 and product B averages 2.9. List two reasons this comparison might be misleading.
4. Interview: A stakeholder asks for "the average NPS score category" (Detractor, Passive, Promoter). What would you report instead? Hint: consider which level of measurement these categories have and which summaries are valid at that level.

Descriptive vs. Inferential Statistics

Why it matters. Statistics answers two different kinds of question. "What happened in this dataset?" is descriptive. "What does this dataset tell us about the world beyond it?" is inferential. They use different tools and carry different levels of risk, and mixing them up leads to over-confident claims.

Definitions.

• Descriptive statistics summarize and display the data you actually have: tables, charts, averages, spreads. No claims are made beyond the data. (Chapter 2.)
• Inferential statistics use a sample to draw conclusions about a population, with a quantified measure of uncertainty: confidence intervals, hypothesis tests, regression models, predictions. (Chapters 7 to 11.)

Analogy. A descriptive statement is a photograph: it records what was in front of the camera. An inferential statement is a forecast: it uses what was seen to make a claim about what was not seen, and so it must come with error bars.

   POPULATION  ---- random sampling ---->  SAMPLE
   (unknown mu)                            (data)
        ^                                     |
        |                                     |  descriptive statistics:
        |                                     v  x_bar, s, histograms
        +---- inferential statistics ---- SUMMARIES
              "mu is likely between 3.6 and 4.8"

Aspect	Descriptive	Inferential
Question	What does the data look like?	What can we conclude about the population?
Scope	The observed data only	Beyond the observed data
Tools	Mean, median, SD, charts, tables	Confidence intervals, tests, models
Uncertainty	None about the data itself	Central; must be quantified
Requires probability theory	No	Yes
Typical risk	Misleading summaries	Wrong generalization

The same dataset can be described and used for inference. Below, 200 support-ticket resolution times are summarized (descriptive) and then used to estimate the mean resolution time for all tickets (inferential):

import numpy as np

rng = np.random.default_rng(1)
times = rng.exponential(scale=4.0, size=200)       # resolution times in hours

# Descriptive: statements about these 200 tickets only
x_bar = times.mean()
s = times.std(ddof=1)                               # sample SD (ddof=1 divides by n - 1)
print(f"mean = {x_bar:.2f} h, median = {np.median(times):.2f} h, SD = {s:.2f} h")
# mean = 4.20 h, median = 3.01 h, SD = 4.38 h

# Inferential: a statement about all tickets, with an uncertainty range
se = s / np.sqrt(len(times))                        # standard error of the mean (Section 7.3)
low, high = x_bar - 1.96 * se, x_bar + 1.96 * se    # approximate 95% confidence interval (Section 8.3)
print(f"95% CI for the population mean: ({low:.2f}, {high:.2f}) h")
# 95% CI for the population mean: (3.59, 4.80) h

Key takeaways

• Descriptive statistics summarize the observed data and make no claims beyond it.
• Inferential statistics generalize from sample to population and must quantify uncertainty.
• Inference is only as good as the link between sample and population, which is set by how the data were collected.
• A precise descriptive number (a sample mean to four decimals) is not a precise inferential claim.

🧪 Practice

1. Label each statement as descriptive or inferential: (a) "The 30 patients in our trial had a mean blood pressure drop of 8 mmHg." (b) "The drug lowers blood pressure in adults by 5 to 11 mmHg." (c) "Last quarter's sales were 12% higher than the previous quarter's."
2. Run the ticket example with size=20 instead of size=200. What happens to the confidence interval, and why?
3. A company surveys every one of its 45 employees about job satisfaction. Is inferential statistics needed to describe employee satisfaction at this company? When might it still be useful?
4. Interview: A dashboard shows that users who enabled dark mode have 15% higher retention. A product manager wants to make dark mode the default. What are the gaps between this descriptive finding and the inferential (and causal) claim being made? Hint: consider who chose to enable dark mode, and see Section 2.5 and Section 12.4.

The Role of Uncertainty

Why it matters. If data were perfectly repeatable, we would not need statistics, only arithmetic. Statistics is the discipline of drawing conclusions when the data could have come out differently. Understanding where uncertainty comes from, and how it behaves, is what separates a defensible conclusion from a lucky guess.

Sources of uncertainty.

Source	Description	Example
Sampling variability	Different samples give different statistics	Two polls of 1,000 voters disagree by 2 points
Measurement error	The recorded value differs from the true value	A scale reads 70.3 kg for a 70.0 kg person
Natural variation	The process itself is random	Two patients respond differently to the same dose
Model uncertainty	The assumed model may be wrong	Fitting a straight line to a curved relationship

Two broad kinds are worth distinguishing:

• Aleatory uncertainty is inherent randomness (the next coin flip). More data cannot remove it, but can describe it precisely.
• Epistemic uncertainty is lack of knowledge (the true proportion of voters supporting a candidate). More data reduces it.

Probability is the language of uncertainty. Probability theory (Chapters 3 to 6) provides the rules for reasoning about random outcomes. Statistical inference (Chapters 7 to 11) runs those rules in reverse: given observed outcomes, what can we say about the process that produced them?

Uncertainty shrinks, but slowly. The typical error of an average shrinks in proportion to $1/\sqrt{n}$. To halve the uncertainty you need four times the data; to cut it by 10 you need 100 times the data. The simulation below estimates a fair coin's heads probability with different numbers of flips:

import numpy as np

rng = np.random.default_rng(0)
for n in [10, 100, 1_000, 10_000]:
    # 5,000 repeated experiments, each flipping a fair coin n times
    p_hats = rng.binomial(n, 0.5, size=5_000) / n
    print(f"n = {n:>6}: spread of p_hat = {p_hats.std():.4f}   theory = {np.sqrt(0.25 / n):.4f}")

n =     10: spread of p_hat = 0.1590   theory = 0.1581
n =    100: spread of p_hat = 0.0497   theory = 0.0500
n =   1000: spread of p_hat = 0.0158   theory = 0.0158
n =  10000: spread of p_hat = 0.0050   theory = 0.0050

 spread of p_hat
 0.16 |*
      |
 0.10 |
      |
 0.05 |      *
 0.02 |              *
 0.00 |____________________*________
       10   100    1000   10000     n  (each 10x increase in n
                                         shrinks the spread ~3.16x)

Key takeaways

• Uncertainty comes from sampling, measurement, natural variation, and the model itself.
• Aleatory uncertainty is irreducible randomness; epistemic uncertainty is lack of knowledge and decreases with data.
• Statistical uncertainty typically shrinks like $1/\sqrt{n}$: four times the data halves the error.
• A conclusion without a statement of its uncertainty is incomplete.

🧪 Practice

1. Classify as aleatory or epistemic: (a) whether tomorrow's die roll is a 6, (b) the average height of adults in a country, (c) the exact arrival time of the next customer at a shop.
2. A poll with 400 respondents has a margin of error of about 5 percentage points. Roughly how many respondents are needed for a margin of 2.5 points? For 1 point?
3. Extend the simulation to a biased coin with $p = 0.1$. Compare the observed spreads to $\sqrt{p(1-p)/n}$. Is the uncertainty larger or smaller than for a fair coin at the same $n$?
4. Interview: A daily-active-users metric rose 2% from yesterday to today. Your manager asks whether the new feature launched today caused it. How do you decide whether 2% is meaningful? Hint: compare the change to the typical day-to-day fluctuation of the metric before the launch.

<a id="12-set-theory-for-probability"></a>

1.2 Set Theory for Probability

Probability assigns numbers to events, and events are sets of outcomes, so set theory provides the grammar for writing probability statements precisely.

Sets, Subsets, and Operations

Why it matters. "The die shows an even number or a number greater than 3" is a sentence in English. To compute its probability we need to turn it into an object we can manipulate. Sets do exactly this: every event becomes a set of outcomes, and every logical connective (or, and, not) becomes a set operation.

Basic vocabulary.

• A set is an unordered collection of distinct objects called elements. We write $x \in A$ for "$x$ is an element of $A$" and $x \notin A$ otherwise.
• Sets are described by roster notation, $A = {2, 4, 6}$, or set-builder notation, $A = {x \in {1, \dots, 6} : x \text{ is even}}$.
• The empty set $\emptyset$ has no elements. In probability it is the impossible event.
• The universal set is the set of everything under consideration. In probability it is the sample space $\Omega$, the set of all possible outcomes (Section 3.1).
• $|A|$ denotes the cardinality (number of elements) of a finite set.
• $A$ is a subset of $B$, written $A \subseteq B$, if every element of $A$ is also in $B$. In event language: "if $A$ happens, then $B$ happens". $A \subset B$ (proper subset) additionally requires $A \neq B$.
• Two sets are equal when $A \subseteq B$ and $B \subseteq A$. This "two inclusions" pattern is the standard way to prove set identities.
• The power set $\mathcal{P}(A)$ is the set of all subsets of $A$. If $|A| = n$, then $|\mathcal{P}(A)| = 2^n$, because each element is either in or out of a subset.

Operations and their meaning as events.

Operation	Notation	Definition	Event language
Union	$A \cup B$	elements in $A$ or $B$ (or both)	"$A$ or $B$ occurs"
Intersection	$A \cap B$	elements in both $A$ and $B$	"$A$ and $B$ both occur"
Complement	$A^c$ (also $\bar{A}$, $A'$)	elements of $\Omega$ not in $A$	"$A$ does not occur"
Difference	$A \setminus B$	elements in $A$ but not in $B$; equals $A \cap B^c$	"$A$ occurs but $B$ does not"
Symmetric difference	$A ,\triangle, B$	elements in exactly one of $A$, $B$	"exactly one of $A$, $B$ occurs"

Sets $A$ and $B$ are disjoint (in probability, mutually exclusive) if $A \cap B = \emptyset$: they cannot happen together.

Algebraic laws. These hold for all sets and mirror the laws of Boolean logic:

Law	Union form	Intersection form
Commutative	$A \cup B = B \cup A$	$A \cap B = B \cap A$
Associative	$(A \cup B) \cup C = A \cup (B \cup C)$	$(A \cap B) \cap C = A \cap (B \cap C)$
Distributive	$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$	$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
Identity	$A \cup \emptyset = A$	$A \cap \Omega = A$
Complement	$A \cup A^c = \Omega$	$A \cap A^c = \emptyset$

Python's built-in set type implements all of these operations directly, which makes it a convenient tool for checking small examples:

omega = set(range(1, 7))        # sample space of one die roll
A = {2, 4, 6}                   # event: "even"
B = {4, 5, 6}                   # event: "greater than 3"

print(A | B)                    # union          -> {2, 4, 5, 6}
print(A & B)                    # intersection   -> {4, 6}
print(omega - A)                # complement     -> {1, 3, 5}
print(A - B)                    # difference     -> {2}
print(A ^ B)                    # symmetric diff -> {2, 5}
print({4, 6} <= A)              # subset test    -> True
print(A.isdisjoint({1, 3}))     # disjoint test  -> True

from itertools import chain, combinations

def power_set(s):
    """All subsets of s: choose r elements for every r from 0 to |s|."""
    s = list(s)
    return [set(c) for c in chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))]

print(len(power_set(omega)))    # 64 = 2^6

Key takeaways

• Events are sets of outcomes; the sample space $\Omega$ is the universal set and $\emptyset$ is the impossible event.
• Union means "or", intersection means "and", complement means "not".
• $A \subseteq B$ means "$A$ implies $B$"; disjoint sets are mutually exclusive events.
• A set with $n$ elements has $2^n$ subsets.
• Prove $A = B$ by showing $A \subseteq B$ and $B \subseteq A$.

🧪 Practice

1. Let $\Omega = {1, 2, \dots, 10}$, $A$ = even numbers, $B$ = multiples of 3. List $A \cup B$, $A \cap B$, $A^c$, $B \setminus A$, and $(A \cup B)^c$.
2. Two coins are tossed. Write $\Omega$, the event $E$ = "at least one head", and the event $F$ = "both coins match". Are $E$ and $F$ disjoint?
3. How many subsets does a 5-element set have? How many of them contain a specific element $x$?
4. Interview: Prove that $A \subseteq B$ if and only if $A \cap B = A$. Hint: prove each direction separately and, for the set equality, show inclusion both ways.

Venn Diagrams

Why it matters. Set expressions with several operations quickly become hard to read. A Venn diagram draws each set as a region inside a rectangle representing $\Omega$, so overlapping events and their combinations can be seen at a glance. It is the most common tool for sanity-checking a probability calculation.

How to read one. The rectangle is $\Omega$. Each circle is an event. Every point in the rectangle belongs to exactly one region, defined by which circles contain it. With two sets there are $2^2 = 4$ regions; with three sets there are $2^3 = 8$.

  Omega
  +--------------------------------------------------+
  |                                                  |
  |   +----------------------+                       |
  |   | A                    |                       |
  |   |   A only    +--------+-------------+         |
  |   |   (A n B^c) | A n B  |             |         |
  |   |             |        |   B only    |         |
  |   +-------------+--------+  (A^c n B)  |         |
  |                 |                    B |         |
  |                 +----------------------+         |
  |                                                  |
  |   neither: (A u B)^c = A^c n B^c                 |
  +--------------------------------------------------+
  Four regions: A only, A and B, B only, neither.

With three sets $A$, $B$, $C$, each region is identified by a membership pattern (1 = inside, 0 = outside):

$A$	$B$	$C$	Region
1	1	1	$A \cap B \cap C$
1	1	0	$A \cap B \cap C^c$
1	0	1	$A \cap B^c \cap C$
0	1	1	$A^c \cap B \cap C$
1	0	0	$A$ only
0	1	0	$B$ only
0	0	1	$C$ only
0	0	0	outside all three, $(A \cup B \cup C)^c$

From picture to formula. Adding $|A| + |B|$ counts the overlap $A \cap B$ twice, so

$$|A \cup B| = |A| + |B| - |A \cap B|.$$

This is the simplest case of the inclusion-exclusion principle (Section 1.3).

Worked example. In a group of 100 students, 60 know Python, 45 know Java, and 25 know both.

• At least one language: $60 + 45 - 25 = 80$.
• Neither: $100 - 80 = 20$.
• Python only: $60 - 25 = 35$. Java only: $45 - 25 = 20$.

The regions $35 + 25 + 20 + 20 = 100$ account for every student, which is a useful check. The same numbers, computed with explicit sets:

students = set(range(100))
python = set(range(0, 60))       # students 0..59 know Python  (60 students)
java = set(range(35, 80))        # students 35..79 know Java   (45 students; 35..59 overlap = 25)

print(len(python & java))        # 25  both
print(len(python | java))        # 80  at least one
print(len(students - (python | java)))  # 20  neither
print(len(python - java))        # 35  Python only
print(len(java - python))        # 20  Java only

Limitations. Venn diagrams are illustrations, not proofs: a picture shows one arrangement of sets, while an identity must hold for all of them. Drawn with circles, they also stop being practical beyond three sets; for four or more, use tables or the inclusion-exclusion formula.

Key takeaways

• The rectangle represents $\Omega$; each circle is an event; each region is a combination of "in" and "out".
• $n$ sets divide $\Omega$ into up to $2^n$ regions.
• Fill a Venn diagram from the innermost region outward, then check that all regions sum to the total.
• Use diagrams to build intuition and catch errors, and algebra to prove results.

🧪 Practice

1. Draw a two-set Venn diagram and shade (a) $A \cap B^c$, (b) $A^c \cup B$, (c) $(A \cap B)^c$.
2. In a survey of 200 people, 120 drink coffee, 90 drink tea, and 50 drink both. How many drink exactly one of the two? How many drink neither?
3. A gym has 150 members: 70 do yoga, 60 do spin, 50 lift weights, 20 do yoga and spin, 15 do spin and weights, 25 do yoga and weights, and 10 do all three. Fill in all 8 regions of a three-set Venn diagram and find how many do none of the activities.
4. Interview: Is it possible to draw a Venn diagram for 4 sets using only circles so that all 16 regions appear? Hint: count how many regions two circles can create when they intersect, and how many new regions a fourth circle can add.

De Morgan's Laws

Why it matters. Many probability questions are phrased as "at least one" or "not all", and these are often hard to compute directly but easy to compute through their complements. De Morgan's laws tell you exactly what the complement of a union or intersection is.

The laws. For any sets $A$ and $B$:

$$(A \cup B)^c = A^c \cap B^c \qquad\qquad (A \cap B)^c = A^c \cup B^c$$

In words: not (A or B) is the same as not A and not B; not (A and B) is the same as not A or not B. Taking a complement swaps union and intersection and complements each piece.

Analogy. "It is not the case that it rained or snowed" means "it did not rain and it did not snow". "It is not the case that the server is up and the database is up" means "the server is down or the database is down" (or both).

Proof of the first law (element chasing).

• $x \in (A \cup B)^c \iff x \notin A \cup B \iff$ ($x \notin A$ and $x \notin B$) $\iff x \in A^c$ and $x \in B^c \iff x \in A^c \cap B^c$.

Since each step is an equivalence, both inclusions hold at once.

General form. For any collection of sets, finite or countably infinite:

$$\left(\bigcup_{i} A_i\right)^c = \bigcap_{i} A_i^c \qquad\qquad \left(\bigcap_{i} A_i\right)^c = \bigcup_{i} A_i^c$$

Proof by membership table. Every outcome falls into one of the four regions of a two-set Venn diagram, so checking all four rows proves each law for all sets:

Region	in $A$	in $B$	$(A \cup B)^c$	$A^c \cap B^c$	$(A \cap B)^c$	$A^c \cup B^c$
$A$ only	1	0	0	0	1	1
$A \cap B$	1	1	0	0	0	0
$B$ only	0	1	0	0	1	1
neither	0	0	1	1	1	1

The third and fourth columns match in every row, and so do the fifth and sixth.

The "at least one" trick. The event "at least one $A_i$ occurs" is $\bigcup_i A_i$. Its complement, by De Morgan, is $\bigcap_i A_i^c$, "none occur". So

$$P(\text{at least one}) = 1 - P(\text{none}).$$

For example, if a system has 3 components that each fail independently with probability 0.1 (independence is defined in Section 3.3), then $P(\text{at least one fails}) = 1 - 0.9^3 = 0.271$. Computing the same quantity directly would require summing over 7 combinations of failures.

The laws are also the reason not (a or b) equals (not a) and (not b) in every programming language:

U = set(range(1, 21))                 # universe: 1..20
A = {n for n in U if n % 2 == 0}      # multiples of 2
B = {n for n in U if n % 3 == 0}      # multiples of 3
comp = lambda S: U - S                # complement relative to U

print(comp(A | B) == comp(A) & comp(B))   # True  (first law)
print(comp(A & B) == comp(A) | comp(B))   # True  (second law)
print(sorted(comp(A | B)))                # [1, 5, 7, 11, 13, 17, 19] -> neither a multiple of 2 nor of 3

# The same identity in Boolean logic, checked for every input combination
for a in (False, True):
    for b in (False, True):
        assert (not (a or b)) == ((not a) and (not b))
        assert (not (a and b)) == ((not a) or (not b))

Key takeaways

• $(A \cup B)^c = A^c \cap B^c$ and $(A \cap B)^c = A^c \cup B^c$; complementing swaps $\cup$ and $\cap$.
• The laws extend to any finite or countable collection of sets.
• "At least one" is the complement of "none": $P(\bigcup A_i) = 1 - P(\bigcap A_i^c)$.
• The same laws govern Boolean logic, so they apply directly to conditions in code.

🧪 Practice

1. Use De Morgan's laws to simplify $(A^c \cup B)^c$ and $(A \cap B^c)^c$.
2. Prove the second law, $(A \cap B)^c = A^c \cup B^c$, by element chasing.
3. Rewrite the condition not (age >= 18 and has_id) without the outer not, and explain in words when it is true.
4. Interview: What is the probability of getting at least one 6 in four rolls of a fair die? Hint: the direct route has many cases. Describe the complementary event first and compute its probability.

Partitions of a Set

Why it matters. A hard problem often becomes easy when split into non-overlapping cases that together cover everything. A partition is the formal version of "consider every case exactly once". It is the structure behind the addition rule for counting (Section 1.3) and the law of total probability (Section 3.4).

Definition. A collection of sets ${B_1, B_2, \dots, B_k}$ is a partition of $\Omega$ if:

1. Nonempty: each $B_i \neq \emptyset$.
2. Pairwise disjoint: $B_i \cap B_j = \emptyset$ for all $i \neq j$ (no outcome is in two blocks).
3. Exhaustive: $B_1 \cup B_2 \cup \dots \cup B_k = \Omega$ (every outcome is in some block).

The sets $B_i$ are called blocks or cells. Partitions can also be countably infinite.

Analogy. The countries on a world map partition the land: every point of land belongs to exactly one country, no two countries overlap, and no land is unassigned.

   Omega
   +---------------+-----------+---------------+
   |               |           |               |
   |      B1       |    B2     |               |
   |               |           |      B4       |
   +-----------+---+-----------+               |
   |           |               |               |
   |    B3     |      B5       |               |
   |           |               |               |
   +-----------+---------------+---------------+
   no gaps, no overlaps: every outcome lies in exactly one block

Common partitions.

• Any event and its complement: ${A, A^c}$ (when $A \neq \emptyset$ and $A \neq \Omega$).
• A die roll by remainder mod 3: ${1, 4}, {2, 5}, {3, 6}$.
• Customers by age bracket, patients by disease status, emails by spam/not spam.

Using a partition to split an event. If ${B_1, \dots, B_k}$ partitions $\Omega$, any event $A$ is the disjoint union $A = (A \cap B_1) \cup \dots \cup (A \cap B_k)$. That means $|A| = \sum_i |A \cap B_i|$, and later $P(A) = \sum_i P(A \cap B_i)$.

Partitions and equivalence relations. Every equivalence relation on a set (reflexive, symmetric, transitive) splits it into equivalence classes, which form a partition. Conversely, every partition defines the relation "is in the same block as". "Has the same remainder mod 3" is an example.

Counting partitions. The number of ways to partition an $n$-element set is the Bell number $B_n$: $1, 1, 2, 5, 15, 52, 203, \dots$ for $n = 0, 1, 2, \dots$. They grow faster than exponentially.

def is_partition(blocks, omega):
    """Check the three defining conditions."""
    if any(len(b) == 0 for b in blocks):                     # 1. nonempty
        return False
    for i in range(len(blocks)):
        for j in range(i + 1, len(blocks)):
            if blocks[i] & blocks[j]:                        # 2. pairwise disjoint
                return False
    return set().union(*blocks) == omega                     # 3. exhaustive

omega = set(range(1, 7))
print(is_partition([{3, 6}, {1, 4}, {2, 5}], omega))   # True  (remainder mod 3)
print(is_partition([{1, 2, 3}, {3, 4}, {5, 6}], omega)) # False (3 is in two blocks)
print(is_partition([{1, 2}, {3, 4}], omega))           # False (5 and 6 are missing)

def partitions(items):
    """Generate every partition of a list: put the first item into an existing block or a new one."""
    if not items:
        yield []
        return
    first, rest = items[0], items[1:]
    for p in partitions(rest):
        for i in range(len(p)):
            yield p[:i] + [[first] + p[i]] + p[i + 1:]   # join block i
        yield [[first]] + p                               # start a new block

print([sum(1 for _ in partitions(list(range(n)))) for n in range(8)])
# [1, 1, 2, 5, 15, 52, 203, 877]  -> Bell numbers

Key takeaways

• A partition splits $\Omega$ into nonempty, non-overlapping blocks that cover everything.
• ${A, A^c}$ is the simplest partition and the one used most often.
• Any event can be split along a partition into disjoint pieces, whose counts or probabilities add.
• Partitions correspond one-to-one with equivalence relations.

🧪 Practice

1. Let $\Omega = {1, \dots, 12}$. Which of the following are partitions? (a) {even, odd}; (b) {multiples of 2, multiples of 3, the rest}; (c) {${1..4}$, ${5..8}$, ${9..12}$}.
2. List all 5 partitions of ${a, b, c}$.
3. A deck of cards is partitioned by suit. Use this partition to count the number of face cards (J, Q, K) in the deck, by summing over blocks.
4. Interview: You need to compute the overall defect rate of a product made in three factories with different volumes and different defect rates. How does a partition help, and what mistake does a simple average of the three defect rates make? Hint: partition the products by factory and weight each block by its size.

Countable and Uncountable Sets

Why it matters. Probability works differently on a finite or "listable" set of outcomes than on a continuum. On a die or the number of emails per day, you can assign a probability to each outcome and add them up. On the interval $[0, 1]$, every single point has probability zero and you need densities instead. The dividing line is countability, and it explains why discrete and continuous random variables (Chapter 4) need different tools.

Definitions.

• A set is finite if it has $n$ elements for some natural number $n$.
• A set is countably infinite if its elements can be listed as a sequence $a_1, a_2, a_3, \dots$ that eventually reaches every element. Formally, there is a bijection (one-to-one correspondence) with $\mathbb{N} = {1, 2, 3, \dots}$.
• A set is countable if it is finite or countably infinite.
• A set is uncountable if no such list exists.

Countable examples.

Set	Listing strategy
Even naturals	$n \mapsto 2n$
Integers $\mathbb{Z}$	$0, 1, -1, 2, -2, 3, -3, \dots$
Pairs $\mathbb{N} \times \mathbb{N}$	walk the grid diagonal by diagonal
Rationals $\mathbb{Q}$	each rational is a pair $p/q$, so list the pairs and skip duplicates
Finite strings over an alphabet	list by length, then alphabetically

The surprising fact is that a set can be "larger" in the subset sense ($\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q}$) and still have the same size in the counting sense.

  Listing the positive rationals diagonal by diagonal (p/q with p + q = 2, 3, 4, ...):

   q=1   q=2   q=3   q=4
  1/1 , 1/2   1/3 , 1/4  ...
       /     /     /
  2/1   2/2   2/3   ...       skip non-reduced fractions such as 2/2, 2/4
      /     /
  3/1   3/2   ...
     /
  4/1   ...

Uncountable: Cantor's diagonal argument. The interval $[0, 1]$ cannot be listed. Suppose a list $r_1, r_2, r_3, \dots$ contained every number in $[0, 1]$, written in decimal:

  r1 = 0. [5] 1  3  9  ...
  r2 = 0.  2 [7] 0  4  ...
  r3 = 0.  8  8 [1] 6  ...
  r4 = 0.  3  3  3 [2] ...
  ...
  Build d by changing the k-th digit of r_k (e.g. to 4, or to 5 if it was 4):
  d  = 0.  4  4  4  4  ...   differs from every r_k in position k, so d is not on the list.

The constructed number $d$ is in $[0, 1]$ but differs from every listed number, which contradicts the assumption. Therefore $[0, 1]$, and hence $\mathbb{R}$, is uncountable. (Choosing replacement digits other than 0 and 9 avoids the ambiguity of decimals like $0.0999\ldots = 0.1$.)

Consequences for probability.

	Countable sample space	Uncountable sample space
Examples	die rolls, number of arrivals	waiting times, heights, $[0, 1]$
Probability of a single outcome	can be positive	zero for continuous distributions
Probability of an event	sum of outcome probabilities	integral of a density
Random variable type	discrete (PMF)	continuous (PDF)
Which subsets get a probability	all of them	only measurable ones (Section 3.5)

Probability is countably additive (Section 3.2): the probability of a countable union of disjoint events is the sum of their probabilities. On $[0, 1]$, the interval is an uncountable union of points, each with probability 0. No contradiction arises, because the addition rule does not extend to uncountable unions.

Generators make "listable" concrete: a countable set is one that a program can enumerate so that every element appears after finitely many steps.

from itertools import count, islice
from math import gcd

def integers():
    """Enumerate Z: 0, 1, -1, 2, -2, ... Every integer appears at a finite position."""
    yield 0
    for n in count(1):
        yield n
        yield -n

def positive_rationals():
    """Enumerate Q+ by diagonals p + q = s, skipping non-reduced fractions."""
    for s in count(2):
        for p in range(1, s):
            q = s - p
            if gcd(p, q) == 1:          # skip duplicates such as 2/4 (= 1/2)
                yield f"{p}/{q}"

print(list(islice(integers(), 9)))            # [0, 1, -1, 2, -2, 3, -3, 4, -4]
print(list(islice(positive_rationals(), 11))) # ['1/1', '1/2', '2/1', '1/3', '3/1', '1/4', '2/3', '3/2', '4/1', '1/5', '5/1']
# No program can do the same for all real numbers in [0, 1].

Key takeaways

• Countable means "can be listed as a sequence"; $\mathbb{N}$, $\mathbb{Z}$, and $\mathbb{Q}$ are countable.
• $\mathbb{R}$ and every interval of positive length are uncountable (Cantor's diagonal argument).
• Countable sample spaces lead to discrete probability (sums); uncountable ones lead to continuous probability (integrals).
• Individual points can have probability 0 while an interval has probability 1, because additivity applies only to countable unions.

🧪 Practice

1. Give an explicit bijection between $\mathbb{N}$ and the set of odd natural numbers.
2. Show that $\mathbb{N} \times \mathbb{N}$ is countable by describing a listing order that reaches every pair, and give the position of the pair $(2, 3)$ in your order.
3. Is the set of all finite binary strings countable? Is the set of all infinite binary sequences countable? Justify each answer.
4. Interview: A random number generator draws $X$ uniformly from $[0, 1]$. Explain how $P(X = x) = 0$ for every $x$ is consistent with $P(0 \le X \le 1) = 1$. Hint: check which kinds of unions the additivity axiom of probability covers.

<a id="13-counting-principles"></a>

1.3 Counting Principles

When all outcomes are equally likely, $P(A) = |A| / |\Omega|$, so computing a probability comes down to counting two sets. This section develops the techniques for counting without listing.

Addition and Multiplication Rules

Why it matters. Listing outcomes one by one works for a die but fails for a deck of cards (2,598,960 five-card hands) or a password space (hundreds of billions of strings). Two rules handle almost every counting problem, either directly or as building blocks for the formulas in the rest of this section.

The addition rule (either/or). If a task can be done in one of $k$ mutually exclusive ways, where way $i$ has $n_i$ options, then the total number of options is

$$n_1 + n_2 + \dots + n_k.$$

In set terms: if $A_1, \dots, A_k$ are pairwise disjoint, $|A_1 \cup \dots \cup A_k| = |A_1| + \dots + |A_k|$. The cases must not overlap; if they do, use inclusion-exclusion (below).

The multiplication rule (first/then). If a task is a sequence of $k$ stages, and stage $i$ can be done in $n_i$ ways no matter which choices were made earlier, then the total number of outcomes is

$$n_1 \times n_2 \times \dots \times n_k.$$

In set terms: $|A_1 \times A_2 \times \dots \times A_k| = |A_1| \cdot |A_2| \cdots |A_k|$. The earlier choices may change which options are available at a later stage, but not how many.

Analogy. Getting dressed: 3 shirts and 4 pairs of trousers give $3 \times 4 = 12$ outfits (multiplication: you choose a shirt and then trousers). Choosing a single item to wear on your feet from 3 pairs of shoes or 2 pairs of sandals gives $3 + 2 = 5$ options (addition: one or the other).

  Menu: 3 starters x 4 mains x 2 desserts

  start ---+--- soup --------+--- pasta ---+--- cake
           |                 |             +--- fruit
           |                 +--- steak ---+--- cake
           |                 |             +--- fruit
           |                 +--- fish  ...
           |                 +--- risotto ...
           +--- salad  ...   (each starter branches into 4 x 2 = 8 leaves)
           +--- bruschetta ...
  Leaves (complete meals): 3 x 4 x 2 = 24

Worked examples.

• A license plate with 3 letters then 4 digits: $26^3 \times 10^4 = 175{,}760{,}000$.
• Passwords of 6 to 8 lowercase letters. Split by length (addition), then count each length (multiplication): $26^6 + 26^7 + 26^8 = 217{,}167{,}790{,}528$.

Brute-force enumeration with itertools.product is a reliable way to check a formula on small cases:

from itertools import product

starters = ["soup", "salad", "bruschetta"]
mains = ["pasta", "steak", "fish", "risotto"]
desserts = ["cake", "fruit"]

meals = list(product(starters, mains, desserts))   # Cartesian product = multiplication rule
print(len(meals))                                  # 24 = 3 * 4 * 2

# Addition over disjoint cases (password length), multiplication within each case
total = sum(26 ** length for length in range(6, 9))
print(f"{total:,}")                                # 217,167,790,528

# Small-scale check of the formula: strings of length 3 over {a, b, c}
print(len(list(product("abc", repeat=3))), 3 ** 3)  # 27 27

Common mistake. Applying the addition rule to overlapping cases. "Bit strings of length 8 that start with 1 or end with 00" is not $2^7 + 2^6$, because strings that do both are counted twice.

Key takeaways

• "Or" across disjoint cases means add; "and then" across stages means multiply.
• The multiplication rule needs the number of options at each stage to be fixed, not the options themselves.
• Split a problem into disjoint cases first, then count each case with the multiplication rule.
• Verify formulas on small inputs by brute-force enumeration.

🧪 Practice

1. How many 4-digit PINs are there (digits 0 to 9)? How many have no repeated digit?
2. A restaurant offers 5 pizzas, each in 3 sizes, with or without extra cheese. How many distinct orders of a single pizza are possible?
3. How many bit strings of length 8 start with 1 or end with 00? (Correct for the overlap.)
4. Interview: How many different functions are there from a set of size $m$ to a set of size $n$? How many of them are one-to-one (assume $m \le n$)? Hint: treat each element of the domain as a stage that chooses its image.

Permutations

Why it matters. Many problems ask how many ways objects can be arranged in order: rankings, seating plans, schedules, passwords without repeated characters. Order-sensitive arrangements of distinct objects are permutations, and they are the most direct application of the multiplication rule.

All $n$ objects. Arranging $n$ distinct objects in a row: there are $n$ choices for the first position, $n - 1$ for the second, and so on, giving

$$n! = n \times (n-1) \times \dots \times 2 \times 1.$$

By convention $0! = 1$: there is exactly one way to arrange nothing (the empty arrangement). This also makes formulas such as $n!/(n-k)!$ work when $k = n$.

$k$ of $n$ objects. Arranging $k$ objects chosen from $n$ distinct objects, where order matters:

$$P(n, k) = n \times (n-1) \times \dots \times (n-k+1) = \frac{n!}{(n-k)!}.$$

This is also written ${}_nP_k$ or $n^{\underline{k}}$ (falling factorial).

  Gold, silver, bronze among 8 runners:

  position:   gold     silver    bronze
  choices:     8    x    7    x    6     = 336 = 8! / 5!
               |         |         |
       anyone of 8  any of the   any of the
                    remaining 7  remaining 6

Circular arrangements. Seating $n$ people around a round table, where rotations count as the same arrangement: each arrangement in a row corresponds to $n$ rotations, so there are $n!/n = (n-1)!$ distinct seatings.

Factorials grow fast. $10! = 3{,}628{,}800$, and $52! \approx 8.07 \times 10^{67}$, so a well-shuffled deck almost certainly has an order no deck has had before. For large $n$, Stirling's approximation $n! \approx \sqrt{2\pi n},(n/e)^n$ is accurate to within about $1/(12n)$ in relative terms.

from itertools import permutations
from math import factorial, perm

print(perm(8, 3))                                 # 336 = 8 * 7 * 6
print(len(list(permutations(range(8), 3))))       # 336 (brute-force check)
print(factorial(10))                              # 3628800
print(f"{float(factorial(52)):.3e}")              # 8.066e+67 orderings of a deck

# All orderings of 3 letters: 3! = 6
print(["".join(p) for p in permutations("ABC")])
# ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']

# Circular seatings of 5 people: fix person 0 in place, permute the rest
people = range(5)
circular = {(0,) + rest for rest in permutations(people[1:])}
print(len(circular), factorial(4))                # 24 24

Key takeaways

• Permutations count ordered arrangements of distinct objects.
• $n!$ arranges all $n$ objects; $P(n, k) = n!/(n-k)!$ arranges $k$ of them.
• $0! = 1$ by convention, which keeps the formulas consistent.
• Circular arrangements divide by the $n$ equivalent rotations: $(n-1)!$.
• Use permutations when swapping two chosen items gives a different outcome.

🧪 Practice

1. How many ways can the letters of the word "MATH" be arranged? How many 2-letter ordered sequences can be formed from them without repetition?
2. In how many ways can 6 people be seated around a round table? In a row?
3. A club with 20 members elects a president, a vice-president, and a treasurer (different people). How many outcomes are possible?
4. Interview: In how many ways can 5 books be arranged on a shelf if two specific books must be next to each other? Hint: glue the two books into a single block, arrange the blocks, then account for the order inside the glued block.

Combinations

Why it matters. Often the order of selection does not matter: a poker hand, a committee, a set of lottery numbers, a sample of 50 customers. Counting these unordered selections is the single most frequently used tool in discrete probability, and it is behind the binomial (Section 5.1) and hypergeometric distributions.

From permutations to combinations. Every unordered selection of $k$ items can be ordered in $k!$ ways. So the ordered count is the unordered count times $k!$:

$$P(n, k) = \binom{n}{k} \cdot k! \quad\Longrightarrow\quad \binom{n}{k} = \frac{n!}{k!,(n-k)!}.$$

$\binom{n}{k}$ is read "$n$ choose $k$" and is called a binomial coefficient. It is also written $C(n, k)$ or ${}_nC_k$.

  Choosing 2 of {A, B, C, D}:

  ordered (permutations, 12):    unordered (combinations, 6):
   AB BA                           {A,B}
   AC CA                           {A,C}
   AD DA          each pair        {A,D}
   BC CB    -->   collapses   -->  {B,C}
   BD DB          2! = 2 -> 1      {B,D}
   CD DC                           {C,D}
                                   12 / 2! = 6 = C(4, 2)

Key identities.

Identity	Formula	Intuition
Symmetry	$\binom{n}{k} = \binom{n}{n-k}$	Choosing who is in equals choosing who is out
Pascal's rule	$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$	A fixed item is either chosen or not
Row sum	$\sum_{k=0}^{n} \binom{n}{k} = 2^n$	Every subset has some size $k$
Binomial theorem	$(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$	Choose which $k$ factors contribute $x$

Pascal's rule builds Pascal's triangle, where each entry is the sum of the two above it and row $n$ lists $\binom{n}{0}, \dots, \binom{n}{n}$:

  n=0             1
  n=1           1   1
  n=2         1   2   1
  n=3       1   3   3   1
  n=4     1   4   6   4   1
  n=5   1   5  10  10   5   1

Permutation or combination?

Question to ask	Permutation	Combination
Does order matter?	Yes	No
Does swapping two chosen items give a new outcome?	Yes	No
Example	Race podium, PIN without repeats	Committee, poker hand, lottery ticket
Formula	$n!/(n-k)!$	$n!/(k!(n-k)!)$

Probability via combinations. A 5-card poker hand is a full house (three of one rank, two of another) with probability:

• Choose the rank of the triple, $13$, and 3 of its 4 suits, $\binom{4}{3}$.
• Choose a different rank for the pair, $12$, and 2 of its 4 suits, $\binom{4}{2}$.

$$P(\text{full house}) = \frac{13 \cdot \binom{4}{3} \cdot 12 \cdot \binom{4}{2}}{\binom{52}{5}} = \frac{3744}{2{,}598{,}960} \approx 0.00144.$$

from math import comb

print(comb(52, 5))        # 2598960 possible poker hands
print(comb(49, 6))        # 13983816 possible 6-of-49 lottery tickets

full_house = 13 * comb(4, 3) * 12 * comb(4, 2)   # rank of triple, suits, rank of pair, suits
print(full_house, full_house / comb(52, 5))      # 3744 0.00144...

def pascal(rows):
    """Each row is built from the previous one by Pascal's rule."""
    row = [1]
    for _ in range(rows):
        print(row)
        row = [a + b for a, b in zip([0] + row, row + [0])]   # add adjacent pairs

pascal(6)
# [1]
# [1, 1]
# [1, 2, 1]
# [1, 3, 3, 1]
# [1, 4, 6, 4, 1]
# [1, 5, 10, 10, 5, 1]

Key takeaways

• Combinations count unordered selections: $\binom{n}{k} = n!/(k!(n-k)!)$.
• $\binom{n}{k} = P(n, k)/k!$: divide out the $k!$ orderings of each selection.
• Symmetry and Pascal's rule are the identities used most often.
• For probabilities, count favourable selections and divide by the total number of selections, using the same notion of "outcome" in both.

🧪 Practice

1. How many 3-person committees can be formed from 10 people? How many if two specific people refuse to serve together?
2. A group has 6 men and 5 women. How many 4-person committees contain exactly 2 women? At least 1 woman?
3. Prove Pascal's rule algebraically from the factorial formula, then explain it in one sentence using a fixed element.
4. Interview: What is the probability that a 5-card hand contains exactly one pair (and nothing better)? Hint: choose the rank of the pair and its suits, then choose three different other ranks and one suit for each. Make sure no extra pair or triple can appear.

Permutations with Repetition

Why it matters. Real arrangements often involve repeated elements. A DNA sequence reuses four bases; the letters of "MISSISSIPPI" repeat; a password may reuse characters. The plain permutation formulas assume all items are distinct and used at most once, so they overcount or undercount here. There are two different situations, and both are called "permutations with repetition".

Case 1: repetition allowed (sampling with replacement, order matters). Each of $k$ positions is filled independently from $n$ types:

$$n^k.$$

Examples: DNA sequences of length 3 over ${A, C, G, T}$: $4^3 = 64$ codons. Binary strings of length 8: $2^8 = 256$.

Case 2: arranging a multiset (repeated identical items). Arrange $n$ items where there are $n_1$ identical copies of type 1, $n_2$ of type 2, ..., $n_k$ of type $k$ ($n_1 + \dots + n_k = n$):

$$\frac{n!}{n_1!, n_2! \cdots n_k!}.$$

Why divide? Pretend the identical items are distinguishable (label them with subscripts). Then there are $n!$ arrangements. Erasing the subscripts merges every group of arrangements that differ only by shuffling identical copies among themselves. Each group has $n_1! \cdots n_k!$ members, so we divide.

  BANANA with labels: B A1 N1 A2 N2 A3  ->  6! = 720 labeled arrangements

  The arrangements
     B A1 N1 A2 N2 A3      B A2 N1 A3 N2 A1      B A3 N2 A1 N1 A2   ...
  all read "BANANA" once labels are erased.
  Each word corresponds to 3! (orders of the A's) x 2! (orders of the N's) = 12 labeled versions.

  distinct words = 720 / (3! x 2! x 1!) = 60

MISSISSIPPI has 11 letters: M once, I four times, S four times, P twice:

$$\frac{11!}{1!,4!,4!,2!} = 34{,}650.$$

The four basic selection models. Combining "order matters?" with "repetition allowed?" gives four formulas for choosing $k$ items from $n$ types. They cover most textbook counting problems:

	Without repetition	With repetition
Order matters	$P(n, k) = \dfrac{n!}{(n-k)!}$	$n^k$
Order does not matter	$\dbinom{n}{k}$	$\dbinom{n + k - 1}{k}$ (stars and bars)

from collections import Counter
from itertools import permutations, product
from math import factorial, prod

def multiset_permutations(word):
    """n! divided by the factorial of each letter's multiplicity."""
    counts = Counter(word)                     # e.g. {'I': 4, 'S': 4, 'P': 2, 'M': 1}
    return factorial(len(word)) // prod(factorial(c) for c in counts.values())

print(multiset_permutations("MISSISSIPPI"))   # 34650
print(multiset_permutations("BANANA"))        # 60
print(len(set(permutations("BANANA"))))       # 60  brute force: a set removes duplicates

# Repetition allowed: every position chooses freely from the alphabet
print(len(list(product("ACGT", repeat=3))))   # 64 = 4^3 codons

Key takeaways

• "With repetition" (reuse allowed, order matters) gives $n^k$.
• "Repeated items" (arranging a multiset) gives $n! / (n_1! \cdots n_k!)$.
• The division removes swaps of identical items, which do not create new arrangements.
• Identify which of the four selection models applies before picking a formula.

🧪 Practice

1. How many distinct arrangements are there of the letters in "STATISTICS"?
2. How many 5-character codes can be formed from the 26 uppercase letters and 10 digits if characters may repeat? If they may not?
3. A coin is flipped 10 times. How many outcome sequences contain exactly 4 heads? Show that the multiset formula and $\binom{10}{4}$ agree.
4. Interview: How many shortest paths are there on a grid from the bottom-left corner $(0, 0)$ to $(5, 3)$, moving only right or up one unit at a time? Hint: write each path as a word made of R's and U's. How many of each letter does every shortest path use?

Multinomial Coefficients

Why it matters. Binomial coefficients split items into two groups: chosen and not chosen. Many problems need more groups: assigning employees to three teams, dealing cards to four players, counting how often each face appears in a series of die rolls. The multinomial coefficient is the many-group generalization, and it leads directly to the multinomial distribution (Section 6.4).

Definition. The number of ways to divide $n$ distinct objects into $k$ labeled groups of sizes $n_1, n_2, \dots, n_k$ (with $n_1 + \dots + n_k = n$) is

$$\binom{n}{n_1, n_2, \dots, n_k} = \frac{n!}{n_1!, n_2! \cdots n_k!}.$$

Two derivations.

1. Sequential choosing. Choose the $n_1$ members of group 1, then $n_2$ of the remaining for group 2, and so on. The product telescopes: $$\binom{n}{n_1}\binom{n - n_1}{n_2}\cdots\binom{n_k}{n_k} = \frac{n!}{n_1!,(n - n_1)!} \cdot \frac{(n - n_1)!}{n_2!,(n - n_1 - n_2)!} \cdots = \frac{n!}{n_1! \cdots n_k!}.$$
2. Labeling. Line up the $n$ objects and write each one's group label underneath. Every assignment is a word with $n_1$ copies of label 1, $n_2$ of label 2, and so on, so the count is the multiset permutation formula from the previous topic. The two problems are the same problem.

With $k = 2$ it reduces to the binomial coefficient: $\binom{n}{k, n-k} = \binom{n}{k}$.

The multinomial theorem. Expanding $(x_1 + \dots + x_k)^n$ means choosing one $x_i$ from each of the $n$ factors. The term $x_1^{n_1} \cdots x_k^{n_k}$ arises once for each way to decide which factors contribute which variable:

$$(x_1 + x_2 + \dots + x_k)^n = \sum_{n_1 + \dots + n_k = n} \binom{n}{n_1, \dots, n_k} x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k}.$$

For example, the coefficient of $x^2 y z^3$ in $(x + y + z)^6$ is $6!/(2!,1!,3!) = 60$.

Labeled vs. unlabeled groups. The formula assumes groups are distinguishable (team A, team B, ...). If groups of equal size have no labels, divide by the number of ways to permute those groups. Splitting 6 people into 3 unlabeled pairs gives $\frac{6!}{2!,2!,2!} / 3! = 15$, not 90.

  12 employees -> Team A (5), Team B (4), Team C (3)

  step 1: choose A    C(12, 5) = 792
  step 2: choose B    C( 7, 4) =  35     (from the 7 remaining)
  step 3: rest -> C   C( 3, 3) =   1
                      ---------------
  total:  792 x 35 x 1 = 27,720 = 12! / (5! 4! 3!)

from collections import Counter
from itertools import product
from math import factorial, prod

def multinomial(*sizes):
    """n! / (n1! n2! ... nk!) where n = sum of group sizes."""
    return factorial(sum(sizes)) // prod(factorial(s) for s in sizes)

print(multinomial(5, 4, 3))        # 27720 ways to form teams A(5), B(4), C(3)

# Check the multinomial theorem by expanding (x + y + z)^6 by brute force:
# each of the 6 factors contributes one variable, so a term is a length-6 word over "xyz".
exponents = Counter(
    tuple(word.count(v) for v in "xyz")       # exponent pattern of x, y, z
    for word in map("".join, product("xyz", repeat=6))
)
print(exponents[(2, 1, 3)], multinomial(2, 1, 3))   # 60 60

# Unlabeled groups: divide by the orderings of interchangeable groups
print(multinomial(2, 2, 2) // factorial(3))         # 15 ways to pair up 6 people

Key takeaways

• $\frac{n!}{n_1! \cdots n_k!}$ counts ways to split $n$ distinct objects into labeled groups of given sizes.
• It equals the number of arrangements of a multiset, because an assignment is a word of labels.
• It gives the coefficients in the expansion of $(x_1 + \dots + x_k)^n$.
• When equal-sized groups are unlabeled, divide by the number of permutations of those groups.

🧪 Practice

1. In how many ways can 52 cards be dealt into four 13-card bridge hands (North, East, South, West)? Leave the answer as a multinomial coefficient.
2. Find the coefficient of $a^3 b^2$ in $(a + b + c)^5$ and of $a^2 b^2 c$ in $(a + b + c)^5$.
3. A die is rolled 12 times. How many sequences of results contain each face exactly twice? What is the probability of this event?
4. Interview: In how many ways can 9 people be split into three teams of 3 for a tournament where the teams have no names? Hint: start from the labeled count and ask how many labeled assignments correspond to the same unlabeled split.

Stars and Bars

Why it matters. Some problems distribute identical items into distinct bins: 10 identical cookies among 4 children, a budget of 20 units across 5 projects, or the number of distinct outcomes when rolling indistinguishable dice. Here the items cannot be told apart, so permutations and combinations of objects do not apply directly. Stars and bars converts the problem into choosing positions in a row of symbols.

The idea. Represent the $k$ identical items as stars ($\star$) and use $n - 1$ bars ($|$) to split them into $n$ bins. Every arrangement of $k$ stars and $n - 1$ bars corresponds to exactly one distribution, and every distribution corresponds to exactly one arrangement.

  10 cookies, 4 children  ->  10 stars and 3 bars

  * * * | * * | | * * * * *       child 1: 3, child 2: 2, child 3: 0, child 4: 5
  | * * * * | * * * | * * *       child 1: 0, child 2: 4, child 3: 3, child 4: 3

  Total symbols: 10 + 3 = 13. Choose which 3 positions hold bars: C(13, 3) = 286

Theorem 1 (bins may be empty). The number of ways to place $k$ identical items into $n$ distinct bins is

$$\binom{k + n - 1}{n - 1} = \binom{k + n - 1}{k}.$$

Equivalently, this counts the non-negative integer solutions of $x_1 + x_2 + \dots + x_n = k$, and the multisets of size $k$ drawn from $n$ types (the "unordered, with repetition" cell of the selection table).

Theorem 2 (every bin gets at least one). Give one item to each bin first, then distribute the remaining $k - n$ freely: $\binom{k-1}{n-1}$. In the picture, this means placing $n - 1$ bars into the $k - 1$ gaps between stars, at most one bar per gap.

Lower bounds in general. For constraints like $x_1 \ge 2$, substitute $y_1 = x_1 - 2 \ge 0$ and solve the reduced problem. Upper bounds (such as $x_i \le 3$) need inclusion-exclusion.

A probability trap. Rolling 3 dice that you cannot tell apart has $\binom{6 + 3 - 1}{3} = 56$ distinct outcome multisets, but these outcomes are not equally likely. ${1, 1, 1}$ arises from one ordered roll, while ${1, 2, 3}$ arises from six. For probability, count ordered outcomes ($6^3 = 216$, all equally likely), unless the problem explicitly describes a model where multisets are equally likely.

from collections import Counter
from itertools import combinations_with_replacement, product
from math import comb

# 10 identical cookies, 4 children
print(comb(10 + 4 - 1, 4 - 1))    # 286  (empty allowed)
print(comb(10 - 1, 4 - 1))        # 84   (each child gets at least one)

# Brute-force check: count integer solutions of x1 + x2 + x3 + x4 = 10
print(sum(1 for x in product(range(11), repeat=4) if sum(x) == 10))      # 286
print(sum(1 for x in product(range(1, 11), repeat=4) if sum(x) == 10))   # 84

# Distinct unordered outcomes of 3 dice (multisets of size 3 from 6 faces)
print(len(list(combinations_with_replacement(range(1, 7), 3))), comb(8, 3))   # 56 56

# ...but unordered outcomes are not equally likely
pairs = Counter(tuple(sorted(r)) for r in product(range(1, 7), repeat=2))
print(len(pairs))                         # 21 unordered outcomes for 2 dice
print(pairs[(1, 1)] / 36, pairs[(1, 2)] / 36)   # 0.0278 vs 0.0556: {1,2} is twice as likely

Key takeaways

• Identical items into distinct bins: $\binom{k + n - 1}{n - 1}$ with empty bins allowed, $\binom{k - 1}{n - 1}$ if every bin must be non-empty.
• The same count gives non-negative integer solutions of $x_1 + \dots + x_n = k$ and multisets of size $k$ from $n$ types.
• Handle lower bounds by substitution; handle upper bounds with inclusion-exclusion.
• Counting distinct unordered outcomes is not the same as counting equally likely outcomes.

🧪 Practice

1. How many non-negative integer solutions does $x_1 + x_2 + x_3 = 7$ have? How many if $x_1 \ge 2$?
2. A bakery sells 5 kinds of donuts. How many different boxes of 12 donuts can you buy? How many if the box must contain at least one of each kind?
3. How many solutions does $x_1 + x_2 + x_3 + x_4 = 12$ have with $0 \le x_i \le 5$ for every $i$? (Combine stars and bars with inclusion-exclusion.)
4. Interview: Two fair dice are rolled. A colleague argues: "There are 21 unordered outcomes and exactly one of them is ${1, 2}$, so $P(\text{sum} = 3) = 1/21$." What is wrong? Hint: list the ordered outcomes that collapse into ${1, 1}$ and into ${1, 2}$, and compare.

Inclusion-Exclusion Principle

Why it matters. The addition rule requires disjoint cases, but real conditions overlap: a number can be divisible by both 2 and 3, a customer can buy both products, a permutation can fix several points. Inclusion-exclusion counts a union of overlapping sets exactly, by alternately adding and subtracting intersections to correct for over- and undercounting.

Two sets. $|A \cup B| = |A| + |B| - |A \cap B|$. The sum $|A| + |B|$ counts the overlap twice, so subtract it once.

Three sets.

$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.$$

Check that each region is counted exactly once. An element in all three sets is added 3 times, subtracted 3 times, and added back once: $3 - 3 + 1 = 1$.

  How often each region is counted by each step (3 sets):

  region            +singles   -pairs   +triple   net
  in exactly 1 set      1         0        0       1
  in exactly 2 sets     2        -1        0       1
  in all 3 sets         3        -3        1       1

General form. For sets $A_1, \dots, A_n$:

$$\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<l} |A_i \cap A_j \cap A_l| - \dots + (-1)^{n+1} |A_1 \cap \dots \cap A_n|.$$

An element in exactly $m \ge 1$ of the sets is counted $\binom{m}{1} - \binom{m}{2} + \dots \pm \binom{m}{m} = 1$ time, because $\sum_{j=0}^{m} (-1)^j \binom{m}{j} = (1 - 1)^m = 0$. The same formula holds with probabilities in place of counts.

Worked example: divisibility. How many integers in $1, \dots, 1000$ are divisible by 2, 3, or 5? Let $A_d$ be the multiples of $d$; then $|A_d| = \lfloor 1000/d \rfloor$, and intersections are multiples of the least common multiple:

$$500 + 333 + 200 - 166 - 100 - 66 + 33 = 734.$$

Worked example: derangements. A derangement is a permutation with no fixed points (nobody gets their own hat back). Let $A_i$ be the permutations that fix item $i$. Any $j$ chosen items can be fixed in $(n - j)!$ ways, so by inclusion-exclusion the number of derangements is

$$D_n = n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \dots = n! \sum_{j=0}^{n} \frac{(-1)^j}{j!}.$$

$D_1, \dots, D_7 = 0, 1, 2, 9, 44, 265, 1854$. The probability that a random permutation is a derangement, $D_n / n!$, approaches $1/e \approx 0.3679$ very quickly.

from itertools import permutations
from math import e, factorial

# Divisible by 2, 3, or 5 in 1..1000: formula vs brute force
N = 1000
formula = (N // 2 + N // 3 + N // 5) - (N // 6 + N // 10 + N // 15) + N // 30
brute = sum(1 for n in range(1, N + 1) if n % 2 == 0 or n % 3 == 0 or n % 5 == 0)
print(formula, brute)                               # 734 734

def derangements(n):
    """Inclusion-exclusion formula: n! * sum (-1)^j / j!"""
    return round(factorial(n) * sum((-1) ** j / factorial(j) for j in range(n + 1)))

def derangements_brute(n):
    return sum(1 for p in permutations(range(n)) if all(p[i] != i for i in range(n)))

print([derangements(n) for n in range(1, 8)])       # [0, 1, 2, 9, 44, 265, 1854]
print([derangements_brute(n) for n in range(1, 8)]) # same list
print(derangements(10) / factorial(10), 1 / e)      # 0.3678794642... 0.3678794411...

Key takeaways

• Inclusion-exclusion corrects the addition rule for overlapping sets: add singles, subtract pairs, add triples, and so on.
• Every element of the union ends up counted exactly once.
• The principle works for counts and for probabilities.
• Combined with complements, it counts objects that avoid all of several "bad" properties (derangements, numbers coprime to $n$, surjective functions).

🧪 Practice

1. How many integers from 1 to 100 are divisible by none of 2, 3, and 5?
2. In a class of 40, 22 study French, 18 study Spanish, 10 study German, 8 study French and Spanish, 5 study French and German, 4 study Spanish and German, and 2 study all three. How many study none of these languages?
3. Count the surjective (onto) functions from a 5-element set to a 3-element set. Hint: subtract the functions that miss at least one target element.
4. Interview: At a party, $n$ guests check their hats and the hats are returned at random. As $n$ grows, does the probability that nobody gets their own hat go to 0, go to 1, or approach something else? Hint: apply inclusion-exclusion to the events "guest $i$ gets their own hat" and compare the resulting series to the series for $e^x$.

Pigeonhole Principle

Why it matters. Some questions ask not "how many?" but "must something happen?". The pigeonhole principle proves that a collision or repetition is guaranteed, without finding it. It explains why hash collisions are unavoidable, why no compression algorithm can shrink every file, and why some coincidences are certain rather than lucky.

Basic form. If $n + 1$ or more objects are placed into $n$ boxes, at least one box contains at least two objects.

Generalized form. If $N$ objects are placed into $k$ boxes, at least one box contains at least $\lceil N/k \rceil$ objects.

Proof idea. If every box held at most $\lceil N/k \rceil - 1$ objects, the total would be at most $k(\lceil N/k \rceil - 1) < N$, a contradiction. The argument is non-constructive: it proves that a crowded box exists without saying which one.

  5 pigeons, 4 holes:

  +-----+-----+-----+-----+
  |  P  |  P  |  P  | P P |   <- whatever the placement, some hole has >= 2
  +-----+-----+-----+-----+

Examples.

Situation	Objects	Boxes	Guarantee
Socks in 3 colours, drawn in the dark	4 socks	3 colours	a matching pair
Birthdays (ignoring Feb 29)	366 people	365 days	two share a birthday
25 people, birth months	25 people	12 months	some month has $\ge 3$ people
16-bit hash of 65,537 strings	65,537 strings	65,536 values	a collision
Losslessly compressing all $n$-bit files	$2^n$ files	$2^n - 1$ shorter strings	some file cannot shrink

Pigeonhole vs. probability. The pigeonhole principle gives certainty at 366 people. Probability shows that a shared birthday becomes likely much earlier: with 23 people the chance is already above 50% (the birthday problem, Section 3.2). Similarly, a 16-bit hash is guaranteed to collide after 65,537 inputs, but a collision typically appears after a few hundred.

import hashlib

def p_shared_birthday(n, days=365):
    """P(at least two of n people share a birthday) = 1 - P(all distinct)."""
    p_distinct = 1.0
    for i in range(n):
        p_distinct *= (days - i) / days
    return 1 - p_distinct

for n in [10, 23, 30, 50, 70]:
    print(n, round(p_shared_birthday(n), 4))
# 10 0.1169
# 23 0.5073   <- likely long before pigeonhole forces it at 366
# 30 0.7063
# 50 0.9704
# 70 0.9992

# A 16-bit hash (first 4 hex digits of SHA-256): collision guaranteed by 65,537 inputs
seen = {}
i = 0
while True:
    key = f"user-{i}"
    h = hashlib.sha256(key.encode()).hexdigest()[:4]   # only 16^4 = 65,536 possible values
    if h in seen:
        print(f"collision after {i + 1} keys: {seen[h]} and {key} -> {h}")
        break
    seen[h] = key
    i += 1
# collision after 766 keys: user-185 and user-765 -> ba3d

Key takeaways

• $N$ objects in $k$ boxes force some box to hold at least $\lceil N/k \rceil$ objects.
• The principle proves existence, not location.
• The hard part is choosing what counts as the "objects" and the "boxes".
• Pigeonhole gives certainty; probability (birthday problem) describes how likely collisions are long before they are certain.

🧪 Practice

1. What is the minimum number of people needed to guarantee that at least 3 share a birth month?
2. A drawer has 10 black and 10 white socks. How many must you draw in the dark to guarantee a matching pair? To guarantee a pair of black socks?
3. Show that among any 5 points placed in a unit square, some two are at distance at most $\sqrt{2}/2$. Hint: divide the square into 4 smaller squares.
4. Interview: An array of length $n + 1$ contains integers from $1$ to $n$. Prove that some value is duplicated, then find one in $O(n)$ time and $O(1)$ extra space without modifying the array. Hint: the proof is pigeonhole; for the algorithm, view index $i \to$ a[i] as a linked list and look for a cycle.

<a id="2-descriptive-statistics"></a>