From the free course Precalculus on Lykke

Probability and Combinatorics

Key concepts: Permutations and combinations · Addition and multiplication rules · Discrete probability distributions · Expected value

Explores counting methods and the rules of probability for compound events and discrete random variables.

Probability and Combinatorics

The study of probability and combinatorics represents the mathematical science of uncertainty and arrangement. While combinatorics provides the tools to count the number of ways discrete events can occur, probability provides the measure of how likely those events are to happen within a defined sample space. To the engineer, these are the tools of risk assessment and reliability; to the data scientist, they are the bedrock of inference; and to the mathematician, they are a beautiful exploration of the structure of sets.

The Calculus of Counting: Combinatorics

Combinatorics is often called "the art of counting without counting." When dealing with large sets, manual enumeration is impossible. Instead, we rely on fundamental principles to derive the size of a sample space or the number of successful outcomes.

The Fundamental Counting Principle

The Fundamental Counting Principle (or the Multiplication Rule for counting) states that if one task can be performed in $n$ ways and a second task can be performed in $m$ ways, then the sequence of two tasks can be performed in $n \times m$ ways. This generalizes to any number of tasks.

Permutations: When Order Defines Identity

A Permutation is an ordered arrangement of a subset of items. In a permutation, the sequence matters: the arrangement $(A, B)$ is distinct from $(B, A)$.

Definition: The Permutation Formula The number of ways to arrange $r$ objects from a set of $n$ distinct objects is given by: $$P(n, r) = \frac{n!}{(n-r)!}$$ where $n!$ (n-factorial) represents the product of all positive integers up to $n$.

Why the division? We start with $n$ choices for the first position, $n-1$ for the second, and so on, until we have filled $r$ positions. The $(n-r)!$ in the denominator "cancels out" the choices we didn't make, leaving only the $r$ factors.

Combinations: The Logic of Selection

A Combination is a selection of items where the order does not matter. If you are choosing a committee of three people from a group of ten, the order in which you pick them is irrelevant; the resulting group is the same.

Definition: The Combination Formula The number of ways to choose $r$ objects from $n$ distinct objects is: $$C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$$

The Intuition: A combination is simply a permutation where we have "divided out" the redundant orderings. Since there are $r!$ ways to arrange $r$ objects, dividing $P(n, r)$ by $r!$ removes the significance of the sequence.

Feature Permutation ($P$) Combination ($C$)
Order Matters? Yes No
Key Keyword Arrange, Sequence, Order Select, Choose, Group
Formula $\frac{n!}{(n-r)!}$ $\frac{n!}{r!(n-r)!}$
Result Size Larger Smaller
Example Race finish (1st, 2nd, 3rd) Hand of cards

Advanced Combinatorics: Repetition and Constraints

In real-world scenarios, we often encounter "Permutations with Repetition" (e.g., arranging the letters in "MISSISSIPPI") or "Combinations with Repetition" (e.g., picking 5 pieces of fruit from a basket of apples, oranges, and bananas).

  • Permutations with Indistinguishable Objects: If there are $n$ total objects where $n_1$ are of one type, $n_2$ of another, etc., the total permutations are $\frac{n!}{n_1! n_2! \dots n_k!}$.
  • Stars and Bars (Combinations with Repetition): The number of ways to choose $r$ items from $n$ types with replacement is $\binom{n+r-1}{r}$.

The Rules of Probability

Probability is the ratio of the size of the event space to the size of the sample space, assuming all outcomes are equally likely: $P(E) = \frac{|E|}{|S|}$.

The Addition Rule (OR Logic)

The Addition Rule is used when we want to find the probability that either Event A or Event B occurs.

  1. Mutually Exclusive Events: If A and B cannot happen at the same time ($A \cap B = \emptyset$), then: $$P(A \cup B) = P(A) + P(B)$$
  2. General Addition Rule (Inclusion-Exclusion): If the events can overlap, we must subtract the intersection to avoid double-counting: $$P(A \cup B) = P(A) + P(B) - P(A \cap B)$$

The Multiplication Rule (AND Logic)

The Multiplication Rule is used to find the probability that both Event A and Event B occur.

  1. Independent Events: If the occurrence of A does not change the probability of B: $$P(A \cap B) = P(A) \times P(B)$$
  2. Dependent Events (Conditional Probability): If the occurrence of A affects B: $$P(A \cap B) = P(A) \times P(B|A)$$ Where $P(B|A)$ is the probability of B given that A has already occurred.
\begin{aligned}
&\text{Derivation of Bayes' Theorem from the Multiplication Rule:} \\
\\
&1. \quad P(A \cap B) = P(A|B)P(B) \\
&2. \quad P(B \cap A) = P(B|A)P(A) \\
&\text{Since } P(A \cap B) = P(B \cap A): \\
&3. \quad P(A|B)P(B) = P(B|A)P(A) \\
&4. \quad P(A|B) = \frac{P(B|A)P(A)}{P(B)}
\end{aligned}

Discrete Probability Distributions

A Random Variable is a numerical description of the outcome of a statistical experiment. When the possible values are countable (e.g., 0, 1, 2, ...), we call it a Discrete Random Variable.

Probability Mass Function (PMF)

The Probability Mass Function (PMF), denoted as $f(x) = P(X = x)$, maps every possible value of a discrete random variable to its probability.

Axioms of Probability Distributions:

  1. $0 \le P(X=x) \le 1$ for all $x$.
  2. $\sum P(X=x) = 1$ (The sum of all probabilities in the sample space must be unity).

Common Discrete Distributions

Distribution Use Case Parameters PMF Formula
Bernoulli Single trial with two outcomes (Success/Failure) $p$ (prob of success) $p^x(1-p)^{1-x}$
Binomial Number of successes in $n$ independent trials $n, p$ $\binom{n}{k} p^k (1-p)^{n-k}$
Poisson Number of events in a fixed interval of time/space $\lambda$ (average rate) $\frac{e^{-\lambda} \lambda^k}{k!}$
Geometric Number of trials until the first success $p$ $(1-p)^{k-1}p$

Worked Example: The Binomial Distribution

Imagine a software system where each request has a 1% chance of failing ($p=0.01$). If the system receives 100 requests, what is the probability that exactly 2 fail?

Using the Binomial PMF: $P(X=2) = \binom{100}{2} (0.01)^2 (0.99)^{98}$ $P(X=2) = 4950 \times 0.0001 \times 0.373 = 0.1848$ (approx 18.5%).

Expected Value and Variance

The Expected Value $E[X]$ is the long-term arithmetic mean of a random variable. It represents the "center of mass" of the distribution.

Calculating Expected Value

For a discrete random variable $X$: $$E[X] = \mu = \sum_{i=1}^{n} x_i P(x_i)$$

It is the weighted average where the weights are the probabilities of each outcome.

Linearity of Expectation

One of the most powerful properties in probability is Linearity of Expectation, which states that the expected value of the sum of random variables is the sum of their expected values, regardless of whether they are independent: $$E[X + Y] = E[X] + E[Y]$$

Variance and Standard Deviation

While the expected value tells us where the distribution is centered, Variance ($\sigma^2$) tells us how "spread out" the values are. $$Var(X) = E[(X - \mu)^2] = E[X^2] - (E[X])^2$$ The Standard Deviation ($\sigma$) is simply the square root of the variance, bringing the units back to the same scale as the original variable.

Common Pitfalls and Paradoxes

Probability is notoriously counter-intuitive. Even experts frequently fall into mental traps.

  1. The Gambler's Fallacy: The mistaken belief that if an event happens more frequently than normal during a given period, it will happen less frequently in the future (and vice-versa). If a fair coin lands heads 10 times in a row, the probability of tails on the 11th flip is still exactly 0.5.
  2. The Birthday Paradox: In a room of just 23 people, there is a >50% chance that two of them share a birthday. This happens because we are looking for any pair of people to match, and the number of pairs grows quadratically ($C(23, 2) = 253$).
  3. Confusing Mutually Exclusive with Independent:
    • Mutually Exclusive: If A happens, B cannot happen. They are highly dependent.
    • Independent: If A happens, it tells you nothing about whether B will happen.

Summary of Key Formulas

Concept Formula
Permutations $P(n, r) = \frac{n!}{(n-r)!}$
Combinations $C(n, r) = \frac{n!}{r!(n-r)!}$
General Addition $P(A \cup B) = P(A) + P(B) - P(A \cap B)$
Conditional Prob $P(A\vert B) = \frac{P(A \cap B)}{P(B)}$
Expected Value $E[X] = \sum x P(x)$
Variance $Var(X) = \sum (x - \mu)^2 P(x)$
Probability and Combinatorics - Precalculus - image 1
Probability and Combinatorics - Precalculus - image 1
Probability and Combinatorics - Precalculus - diagram 1
Probability and Combinatorics - Precalculus - diagram 1
Probability and Combinatorics - Precalculus - diagram 2
Probability and Combinatorics - Precalculus - diagram 2

Source Materials

Study Precalculus on Lykke

This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.

Add the free extensionSign in to open every section

All sections of Precalculus · Browse more course pages

Probability and Combinatorics — Precalculus | Lykke