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.
- 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)$$
- 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.
- Independent Events: If the occurrence of A does not change the probability of B: $$P(A \cap B) = P(A) \times P(B)$$
- 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:
- $0 \le P(X=x) \le 1$ for all $x$.
- $\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.
- 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.
- 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$).
- 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)$ |
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